= 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. \b[<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\geq1$ 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\geq1$ with value at least $\mathrm{OPT}/\alpha$; an equivalent convention uses ratios at most one. The metric-tour question uses the minimization convention.
Back to article page
