 Solution

A decision problem belongs to NP if every yes-instance has a polynomial-length certificate verifiable by a deterministic polynomial-time algorithm. It is NP-hard if every problem in NP has a polynomial-time many-one reduction to it. It is NP-complete if it is both NP-hard and in NP.

A polynomial-time algorithm for any NP-complete problem would therefore give one for every problem in NP, implying $\mathrm{P}=\mathrm{NP}$. Conversely, if $\mathrm{P}=\mathrm{NP}$, all NP-complete decision problems have polynomial-time algorithms. NP-completeness does not unconditionally prove that polynomial-time solution is impossible. Optimization problems such as minimum tour cost are described as NP-hard, while their threshold decision versions can be NP-complete.

For a minimization problem with nonnegative costs, an approximation algorithm of ratio $\alpha \ge 1$ is a polynomial-time algorithm returning a feasible solution of cost at most $\alpha$ times the optimum on every instance. For maximization, one often uses $\alpha \ge 1$ with value at least $\mathrm{OPT}/\alpha$; an equivalent convention uses ratios at most one. The metric-tour question uses the minimization convention.