Pseudo-Polynomial Time Complexity

Definition

Pseudo-Polynomial Time Complexity

For a numerical instance , let and be its binary and unary encoding lengths. An algorithm has pseudo-polynomial time complexity if

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 .

Equivalently, for standard explicit encodings, a pseudo-polynomial bound is polynomial in and the largest numerical magnitude .

Why the Encoding Matters

For a positive integer with binary length ,

Thus : binary encoding is compact. A bound becomes in terms of bit-length. Unary encoding uses 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 , then

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: for numbers and target .
• Knapsack: for capacity , or for a bound on total value.

The parameters are numerical magnitudes, not encoding lengths.

Already polynomial in binary length

A bound is polynomial in the binary input length. It is also pseudo-polynomial, but the ordinary polynomial-time guarantee is more informative.