Strong NP-Hardness Rules Out FPTAS

Definition

Strong NP-Hardness Rules Out FPTAS

Let $\Pi$ be an NP-optimisation problem with an integer objective function $f_{\Pi }$. Suppose that, on every instance $I$, the optimal value satisfies

$$\mathrm{OPT}(I)<p(||I|{|}_{\mathrm{una}}),$$

where $||I|{|}_{\mathrm{una}}$ is the unary encoding of $I$, for some polynomial $p$.

If $\Pi$ is strongly NP-hard, then $\Pi$ does not admit an FPTAS unless P = NP.

Proof

Proof by contradiction

Assume P ≠ NP and let $A$ be an FPTAS for $\Pi$. Write $b=\Vert I{\Vert }_{\mathrm{bin}}$ and $u=\Vert I{\Vert }_{\mathrm{una}}$ for the lengths of the binary and unary encodings. Enlarge the polynomial $p$ if necessary so that $p(u)>1$.

(1) Make the approximation exact

Choose $\epsilon =1/p(u)$. The approximation error satisfies

$$\begin{array}{rl}0\le |f_{\Pi }(A(I,\epsilon ))-\mathrm{OPT}(I)|& \le \epsilon \mathrm{OPT}(I)\\ & =\frac{\mathrm{OPT}(I)}{p(u)}<1.\end{array}$$

Integer objective values therefore force equality with the optimum: this is exact optimisation via integrality. The resulting exact algorithm takes time

$$T(I)\le \mathrm{poly}(b,p(u))=\mathrm{poly}(b,u).$$

This is only pseudo-polynomial in general: $u$ can be exponential in $b$.

(2) Use strong NP-hardness

By strong NP-hardness, some NP-hard restriction bounds every numerical parameter by a polynomial $q(b)$. There are at most $b$ such parameters, so

$$u\le \underset{\text{other input}}{\underbrace{b}}+\underset{\text{unary numerical parameters}}{\underbrace{bq(b)}}=\mathrm{poly}(b).$$

Substituting this bound gives

$$T(I)\le \mathrm{poly}(b,u)=\mathrm{poly}(b).$$

Thus the algorithm is exact and runs in polynomial time on this restriction.

(3) Solve the NP-hard decision problem

Compute the optimum and compare it with the decision threshold. This solves an NP-hard problem in polynomial time, implying P = NP—a contradiction.