Pseudo-Polynomial Time Complexity

complexity-theory

Definition

Pseudo-polynomial time complexity

Pseudo-polynomial time complexity is a time complexity that is polynomial in the encoded input length and in the numeric values of selected integer parameters, but not necessarily polynomial in the bit-lengths of those parameters.

Formally, fix an encoding of instances. For an instance $I$, let

$$m(I)=|I|$$

be its encoded input length. Let $q_1(I),\dots ,q_k(I)$ be numeric parameters of $I$, such as capacities, targets, or total weights. An algorithm $A$ runs in pseudo-polynomial time if there is a polynomial $p$ such that, for every instance $I$,

$$T_A(I)\le \mathrm{poly}(m(I),q_1(I),\dots ,q_k(I)).$$

This differs from ordinary polynomial time, which requires fixed constants $C,c$ such that

$$T_A(I)\le C\cdot m(I{)}^c$$

for every instance $I$. In pseudo-polynomial time, the bound may depend polynomially on numeric values $q_j(I)$ that can be exponentially larger than their encoded bit-lengths.

Equivalently, if

$${\ell }_j(I)=\lceil {\log }_2(q_j(I)+1)\rceil ,$$

then $q_j(I)\approx 2^{{\ell }_j(I)}$. Thus a runtime polynomial in $q_j(I)$ may be exponential in ${\ell }_j(I)$ when the parameters are given in binary encoding.

Encoding

The distinction matters because binary encoding is compact. If $W$ is a numeric field of an instance $I$, define its bit-length by

$${\ell }_W(I)=\lceil {\log }_2(W+1)\rceil .$$

A runtime $O(nW)$ is polynomial in $n$ and $W$, but it is not necessarily polynomial in $n$ and ${\ell }_W(I)$, because

$$W\approx 2^{{\ell }_W(I)}.$$

Thus

$$O(nW)=O\left(n{2}^{{\ell }_W(I)}\right)$$

up to constant factors in the exponent.

If the same numeric input were written in unary, then the length of the encoding of $W$ would be $\Theta (W)$. Under that encoding, an $O(nW)$ algorithm would be polynomial in the input length. This is why pseudo-polynomial time is often described as polynomial time under unary encoding.

Consequences

Pseudo-polynomial algorithms explain the difference between weakly NP-hard and strongly NP-hard problems.

A weakly NP-hard problem may admit a pseudo-polynomial algorithm. Its hardness comes from the possibility that numeric values are exponentially large compared with their binary encodings.

A strongly NP-hard problem cannot admit a pseudo-polynomial algorithm unless $\mathrm{P}=\mathrm{NP}$. Its hardness remains even when numeric values are polynomially bounded in the input size.

Non-example

An algorithm with runtime

$$O(n^2\log W)$$

is ordinary polynomial time with respect to the binary input length, because $\log W$ is the size of the binary representation of $W$. It is not merely pseudo-polynomial.

Examples

Subset sum

The subset sum problem with numbers $w_1,\dots ,w_n$ and target $W$ has a dynamic programming algorithm with runtime

$$O(nW).$$

This is pseudo-polynomial. It is polynomial in the number of items and in the target value $W$, but it can be exponential in the bit-length ${\ell }_W(I)$ of the target.

Knapsack

The knapsack problem has dynamic programming algorithms with runtimes such as

$$O(nS)$$

where $S$ is the capacity, or

$$O(nV)$$

where $V$ is a bound on total value. These bounds are pseudo-polynomial because $S$ and $V$ are numeric magnitudes, not encoding lengths.