Bi Knapsack Has No FPTAS Unless P Equals NP

Definition

Bi Knapsack has no FPTAS unless P equals NP

The Bi Knapsack problem admits no FPTAS unless $\mathrm{P}=\mathrm{NP}$, despite admitting a pseudopolynomial dynamic programme. The argument uses the known NP-hardness of this cardinality optimisation problem.

Proof

An error smaller than one item forces exactness

Choose inverse-polynomial accuracy

Suppose an FPTAS exists. For an instance with $n\ge 1$ items, run it with $\epsilon =1/(n+1)$. Its time is polynomial in the binary input length and $1/\epsilon =n+1$, hence polynomial in the input length. For $n=0$, the empty solution is already optimal.

Bound the absolute loss

Let $q=\mathrm{OPT}$ and let $z$ be the cardinality of the returned feasible subset. Then $0\le z\le q\le n$, and
$z\ge (1-\epsilon )q=q-\frac{q}{n+1}.$
Since $q/(n+1)\le n/(n+1)<1$, we obtain $q-1<z\le q$.

Both $z$ and $q$ are integers. No integer smaller than $q$ is greater than $q-1$, so $z=q$. The same conclusion holds when $q=0$ by feasibility.

Contradict NP-hardness

This gives an exact polynomial-time algorithm for the NP-hard optimisation problem, and therefore a polynomial-time algorithm for its associated threshold decision problem. Thus an FPTAS would imply $\mathrm{P}=\mathrm{NP}$.

Why pseudopolynomial time does not suffice

Exact optimisation via integrality generally yields pseudopolynomial time when the objective bound is polynomial only in unary input length. Here the stronger bound $\mathrm{OPT}\le n$ is already polynomial in binary input length. Consequently the precision needed for exactness is affordable to an FPTAS in ordinary polynomial time.

The capacities may be huge and make dynamic programming expensive, but the objective still counts at most $n$ items. These are different quantities. The obstruction is not strong NP-hardness; it is the combination of NP-hardness and a polynomially bounded integer objective.