NP-complete

A problem is NP-complete if it satisfies two conditions: it is in the complexity class NP (a proposed solution can be verified in polynomial time), and it is NP-hard (every problem in NP can be reduced to it in polynomial time). The concept was formalized by Stephen Cook and Leonid Levin independently in 1971, with the proof that the Boolean satisfiability problem is NP-complete — the Cook-Levin Theorem. This result established that SAT is not merely one hard problem among many, but a universal hard problem: solve SAT efficiently, and you solve every problem in NP efficiently.

The significance of NP-completeness extends far beyond theoretical computer science. It is a boundary marker that separates tractable problems from intractable ones in practice, even though the formal question of whether P = NP remains open. When a systems designer discovers that their optimization problem is NP-complete, they are not receiving a technical inconvenience. They are receiving a mathematical diagnosis: the problem's structure is sufficiently general that no algorithm can exploit its regularity in all cases. The designer must then choose between approximation algorithms, heuristic search, restriction to tractable fragments, or acceptance of exponential runtime for small instances.

The NP-completeness framework has been extended to other complexity classes: PSPACE-complete for games and planning problems, #P-complete for counting problems, and EXPTIME-complete for certain decision procedures. These completeness results share a common structure: they identify a canonical hard problem for a class and show that all other problems in the class reduce to it. The framework is a kind of computational taxonomy — a way of classifying problems by their inherent difficulty rather than by their surface features.

In the context of constraint satisfaction and automated reasoning, NP-completeness is not merely a theoretical result but a design constraint. A verification engineer who encodes a safety property as a SAT formula is deliberately placing their problem in the NP-complete class, trading generality for the availability of highly optimized solvers. The choice to use an NP-complete formalism is a systems design decision, not a theoretical concession.