What NP-Completeness Says About Approximation

Decision Hardness Is Not Approximation Hardness

NP-completeness is a statement about decision problems: instances have yes-or-no answers, and certificates for yes-instances can be checked in polynomial time. An optimization problem instead asks for a feasible solution with the best objective value. The two viewpoints are connected, but a reduction that preserves only the yes-or-no answer need not preserve enough information about objective values to rule out good approximations.

For example, the decision version of Vertex Cover asks whether a graph has a vertex cover of size at most \(k\). Its optimization version asks for a smallest vertex cover. An exact optimizer would answer the decision question: compute the minimum cover size and compare it with \(k\). Thus, if the decision problem is NP-complete, an exact polynomial-time optimizer would imply \(P=NP\). The conclusion is conditional: NP-completeness does not prove that \(P\ne NP\).

An approximation algorithm is different. For a minimization problem, it may return a feasible solution that is larger than optimal, but it promises that the returned objective value is within a stated factor of the optimum. Such a guarantee need not reveal whether the optimum lies just above or just below a decision threshold. That is why the existence of a polynomial-time approximation algorithm, even with a useful constant factor, does not follow or fail merely from the word “NP-complete.”

The positive-optimum condition matters for these ratio statements. If the optimum is zero, a multiplicative ratio written as \(C/\mathrm{OPT}\) or \(\mathrm{OPT}/A\) is not defined. Some definitions separately require exact handling of zero-optimum instances; otherwise, those instances must be handled by an additional argument. We will make the positive-optimum assumption explicit whenever we use a ratio to distinguish decision cases.

What an Ordinary Reduction Does—and Does Not—Preserve

A polynomial-time many-one reduction from a decision problem \(L\) to a decision problem \(D\) maps each input \(x\) to an instance \(f(x)\) in polynomial time, with \(x\in L\) exactly when \(f(x)\) is a yes-instance of \(D\). If \(L\) is NP-hard, this establishes that solving \(D\) is at least as hard as solving \(L\). But the equivalence of yes and no answers alone says nothing about how far apart the optimization values of the two cases are.

Suppose a minimization decision question asks whether \(\mathrm{OPT}\le k\). A reduction might ensure that yes-instances have optimum at most \(k\), while no-instances have optimum at least \(k+1\). That is an additive separation of one. If \(k\) is large, the ratio between the two bounds is close to one. A constant-factor approximation can therefore return values compatible with either case.

Gap-Preserving Reductions

To turn approximation performance into a decision procedure, a reduction needs a promise gap: yes-instances must map to optimization instances with one objective bound, and no-instances to instances separated far enough from that bound. The reduction is called gap-preserving in the relevant sense if it preserves this separation. The following result gives the precise comparison needed for minimization.

Proof. Assume such an approximation algorithm exists. Given an input to the promise decision problem, compute its reduced minimization instance and run the approximation algorithm, obtaining a feasible solution of cost \(C\). If the input is a yes-instance, then \(0<\mathrm{OPT}\le a\), so the guarantee gives \(C\le\rho\,\mathrm{OPT}\le\rho a<b\). If the input is a no-instance, every feasible solution has cost at least the optimum, so \(C\ge\mathrm{OPT}\ge b\). Thus comparing \(C\) with \(b\) distinguishes the cases: answer yes when \(C<b\), and no when \(C\ge b\). The reduction, approximation algorithm and comparison all run in polynomial time. This would solve an NP-hard promise decision problem in polynomial time, implying \(P=NP\). \(\square\)

The strict inequality \(\rho a<b\) is essential to this argument: it puts every approximate yes-case cost strictly below every no-case feasible cost. The condition \(a>0\) also states explicitly that the multiplicative guarantee is being applied where its ratio interpretation is meaningful.

The maximization version has the inequalities reversed. If a reduction maps yes-instances to instances with \(\mathrm{OPT}\ge b>0\) and no-instances to instances with \(\mathrm{OPT}\le a\), where \(0\le a<b\), then a \(\rho\)-approximation distinguishes the cases whenever \(b/\rho>a\). Indeed, on a yes-instance its returned value is at least \(\mathrm{OPT}/\rho\ge b/\rho>a\); on a no-instance every feasible value is at most \(\mathrm{OPT}\le a\). Comparing the returned value with \(a\) decides the promise problem. This argument uses the definition of a feasible maximization value and the approximation guarantee, not a separate hardness theorem.

Why a PTAS Can Also Be Ruled Out

A PTAS gives a factor \(1+\varepsilon\), not an arbitrarily chosen factor less than one. If a fixed objective gap has \(0<a<b\), choose a fixed \(\varepsilon>0\) small enough that \((1+\varepsilon)a<b\). The PTAS algorithm for that one fixed \(\varepsilon\) then triggers the minimization theorem. Since \(\varepsilon\) is fixed rather than part of the input, the PTAS definition promises polynomial running time for this algorithm. Thus a suitable gap-preserving reduction can rule out a PTAS unless \(P=NP\).

This is a conditional conclusion, not a proof that a PTAS is impossible in every NP-hard optimization problem. The reduction must establish the required gap, and the conclusion that no such algorithm exists depends on \(P\ne NP\). Conversely, if a problem has no known gap-preserving reduction of the needed strength, NP-completeness by itself does not settle whether it admits a constant-factor approximation or a PTAS.

The Zero-Optimum Pitfall

A common incorrect step is to apply a positive-optimum ratio guarantee to an instance with optimum zero. For example, let \(G\) have \(V(G)=\{1,2\}\) and \(E(G)=\varnothing\). Its minimum vertex cover has size \(0\), since the empty set covers every edge. The set \(\{1\}\) is also a feasible cover, with cost \(1\). If a definition only guarantees a ratio when \(\mathrm{OPT}>0\), it says nothing about the returned cost on this instance. One cannot infer \(C\le\rho\cdot0=0\) from a guarantee whose hypothesis fails.

To repair such an argument, require \(a>0\) for the yes-case gap, as in the theorem, or state and justify a separate guarantee for zero-optimum instances. In a minimization problem with nonnegative costs, a special zero-case guarantee might require the algorithm to return cost \(0\) whenever \(\mathrm{OPT}=0\). That condition is additional; it must not be silently inferred from a ratio defined only for positive optima.

The practical distinction is therefore precise. Exact optimization can solve the associated threshold decision problem by comparing the optimum with the threshold, so NP-completeness rules out a polynomial-time exact algorithm unless \(P=NP\). Approximation hardness needs more: a reduction that separates the objective values enough that the promised approximation guarantee still leaves the yes- and no-cases distinguishable. Without that quantitative separation, decision hardness alone does not answer the approximation question.