Reducibility and Completeness
Completeness identifies the hardest problems in a class as those to which every member reduces, capturing the essence of the class.
The general pattern
For a complexity class C, a problem is C-complete if it is in C and every problem in C reduces to it (using reductions weaker than C itself). Complete problems are the hardest in the class and embody its full difficulty. Solving one efficiently within a weaker class would collapse C into that class.
Why completeness is powerful
A complete problem is a single representative that captures an entire class. Proving something about it, positive or negative, transfers to the whole class. This is why SAT, being NP-complete, concentrates the P vs NP question into one concrete problem.
Complete problems across classes
- NP-complete: SAT, clique, Hamiltonian cycle
- PSPACE-complete: quantified Boolean formulas, many games
- EXPTIME-complete: generalized chess and Go
- P-complete: circuit value problem (hardest to parallelize)
Matching the reduction to the class
The reductions used must be weaker than the class being studied, or completeness is meaningless. NP-completeness uses polynomial-time reductions. For classes inside P, such as defining P-completeness, weaker log-space reductions are used, so that the reduction cannot itself do the class's hard work.
P-completeness and parallelism
A P-complete problem is the hardest to parallelize: if any P-complete problem had a fast parallel (low-depth circuit) algorithm, all of P would parallelize well. The circuit value problem is the canonical example, suggesting some polynomial-time problems are inherently sequential.
The unifying view
Completeness turns a class from an abstract collection into something with a concrete hardest member. Across the complexity landscape, complete problems serve as anchors: they are where lower-bound efforts focus and where the fate of the whole class is decided.