Pseudo-Polynomial Time Complexity

Definition

Pseudo-Polynomial Time Complexity

For a numerical instance $I$, let $b(I)$ and $u(I)$ be its binary and unary encoding lengths. An algorithm $A$ has pseudo-polynomial time complexity if

$$T_A(I)\le \mathrm{poly}(u(I)).$$

Here poly notation means a fixed polynomial bound. The running time may depend polynomially on numerical values, rather than only on their bit-lengths. Ordinary polynomial time instead requires $T_A(I)\le \mathrm{poly}(b(I))$.

Equivalently, for standard explicit encodings, a pseudo-polynomial bound is polynomial in $b(I)$ and the largest numerical magnitude $M(I)$.

Why the Encoding Matters

For a positive integer $W$ with binary length $\ell$,

$$\begin{array}{rl}\ell & =\lfloor {\log }_{2}W\rfloor +1,\\ 2^{\ell -1}& \le W<2^{\ell }.\end{array}$$

Thus $W=\Theta (2^{\ell })$: binary encoding is compact. A bound $O(nW)$ becomes $O(n{2}^{\ell })$ in terms of bit-length. Unary encoding uses $\Theta (W)$ symbols instead, making the same bound polynomial in the encoded input length.

Bounded Numbers and NP-Hardness

If every numerical magnitude is at most a fixed polynomial $q(b)$, then

$$\begin{array}{rl}u& \le b+bq(b)=\mathrm{poly}(b),\\ T_A(I)& \le \mathrm{poly}(u)=\mathrm{poly}(b).\end{array}$$

This is why standard weakly NP-hard problems become polynomial-time solvable on bounded-number instances. A strongly NP-hard problem remains NP-hard on some such restriction, so it cannot admit a pseudo-polynomial algorithm unless P = NP.

Example

Subset sum and knapsack

Dynamic programming gives pseudo-polynomial bounds:

• Subset sum: $O(nW)$ for $n$ numbers and target $W$.
• Knapsack: $O(nS)$ for capacity $S$, or $O(nV)$ for a bound $V$ on total value.

The parameters $W,S,V$ are numerical magnitudes, not encoding lengths.

Already polynomial in binary length

A bound $O(n^2\log (1+W))$ is polynomial in the binary input length. It is also pseudo-polynomial, but the ordinary polynomial-time guarantee is more informative.