Computability theory splits problems into solvable and unsolvable. But a problem solvable in principle may take so long as to be useless in practice. Complexity theory therefore introduces a second distinction, between tractable and intractable problems. The most important class on the tractable side is P: the set of problems decidable in polynomial time by a deterministic machine.
The definition
For a deterministic Turing machine M that halts on every input, the running time is the function t(n) giving the maximum number of steps M takes on an input of length n. We look at the worst case, not the average.
TIME(t(n)) is the class of languages decided by some deterministic machine in time O(t(n)).
P = TIME(n) ∪ TIME(n²) ∪ TIME(n³) ∪ …
that is the union of TIME(nᵏ) over all k. A problem is in P if some algorithm solves it in a number of steps bounded by a polynomial in the length of the input.
Why a polynomial
Choosing the polynomial as the boundary may look arbitrary: an n¹⁰⁰ algorithm is hardly practical. The reasons are sounder than they seem.
- Robustness across models: a multitape machine is simulated by a single-tape one with quadratic slowdown; a register model or a real programming language is simulated with polynomial slowdown. P stays the same whichever reasonable model is used.
- Closure under composition: if a polynomial algorithm calls a polynomial subroutine a polynomial number of times, the result is still polynomial. This lets us build complex algorithms by combining simple pieces.
- Distance from the exponential: the gap between n³ and 2ⁿ is enormous. Doubling a machine's speed lets an n³ algorithm handle instances about 26% larger; a 2ⁿ algorithm, instances larger by just one element.
- Experience: when a polynomial algorithm is found for a natural problem, the exponent is often reduced to small values later.
Input encoding matters
"Input length" means the number of symbols used to write it, and this is where many traps lie.
A number N written in binary takes about log₂ N bits. An algorithm that performs N steps is therefore exponential in the input length, not linear. For example, testing whether N is prime by trying every divisor up to √N takes about √N = 2^(log₂N / 2) steps: exponential in the number of digits.
A reasonable encoding is always required: binary or decimal for numbers, lists of nodes and edges or adjacency matrices for graphs. Unary encoding, in which the number 5 is written 11111, is considered unreasonable because it artificially inflates the input length and makes non-polynomial algorithms look polynomial.
Pseudo-polynomial algorithms
The knapsack problem with capacity W and n items is solved by dynamic programming in time O(nW). It looks polynomial, but W is a number, and its binary representation has length log W. The running time is therefore exponential in the input length. Algorithms of this kind are called pseudo-polynomial: they are fast when the numbers involved are small, but they do not show the problem is in P.
Examples of problems in P
- Graph reachability: given a directed graph with two nodes s and t, is there a path from s to t? A breadth-first search examines each node and each edge at most once.
- Coprime numbers: given x and y, is their greatest common divisor 1? Euclid's algorithm at least halves one of the numbers every two steps, so the number of iterations is proportional to the number of digits.
- Membership in a context-free language: given a grammar in Chomsky normal form and a string of length n, the CYK algorithm decides in O(n³) time.
- Primality: deciding whether a number written in binary is prime is in P. The AKS algorithm proved it; this is a case where membership in P was far from obvious.
- Linear programming: optimizing a linear function under linear constraints is in P, thanks to the ellipsoid method and interior-point methods, even though the simplex method, widely used in practice, has exponential worst cases.
What P does not guarantee
Being in P is a theoretical guarantee, not a practical one. An O(n⁸) algorithm with large constants may be unusable, while a well-optimized exponential algorithm may comfortably solve every instance that actually matters. P measures how worst-case cost grows as the input grows, which is a valuable indicator, but it does not replace measurements in the field.
In my work the question "is it in P?" mainly helps choose a strategy: if a problem is in P I look for the right algorithm; if it seems not to be, I change approach at once and think about constraints, approximations or limits on size.
In short
- P is the class of problems decidable by a deterministic machine in worst-case polynomial time.
- The polynomial boundary is robust across models of computation and closed under composition.
- Input length is measured with reasonable encodings: a number N takes about log N bits.
- Pseudo-polynomial algorithms, such as the one for knapsack, do not prove membership in P.
- Reachability, coprimality, CYK, primality and linear programming are in P.
