pseudopolynomialtime

Pseudopolynomial time describes a running time that is polynomial in the numeric value of the input, rather than in the length of the input’s encoding. In other words, an algorithm is pseudopolynomial if its running time is polynomial in the actual numbers appearing in the instance (such as weights or sums) but not necessarily polynomial in the size of the binary representation of those numbers.

Common examples are dynamic programming algorithms for knapsack and subset sum. The knapsack DP runs in O(nW) time, where n is the number of items and W the capacity. The subset sum DP runs in O(nW) as well, with W the target sum. These procedures are polynomial in n and W, but W can be exponential in the number of bits needed to represent W, so the running time may be exponential in input size.

Pseudopolynomial time is closely related to weakly NP-complete problems such as knapsack and subset sum; such problems admit polynomial-time algorithms when the numeric values are small, but remain intractable in general for binary-encoded inputs. If the numbers are given in unary, a pseudopolynomial algorithm becomes polynomial in input length, effectively removing the gap between numeric value and input size.

In practice, pseudopolynomial algorithms are useful for instances with small numerical values or when weights are bounded, but they can be impractical for large weights. The existence of a pseudopolynomial algorithm does not imply P = NP, and these algorithms are typically considered in the context of weak NP-hardness rather than strong, universal tractability.