NP-completeness

A problem is NP-complete if it belongs to NP and every problem in NP is polynomially reducible to it. NP-complete problems are, in a formal sense, the hardest problems in NP: if any one of them can be solved in polynomial time, then P = NP and the entire class of NP problems becomes tractable.

The canonical example is the Boolean satisfiability problem (SAT), proved NP-complete by Stephen Cook (1971) and independently by Leonid Levin. Thousands of NP-complete problems have since been identified across combinatorics, graph theory, scheduling, and cryptography. The Cook-Levin theorem established the structure of the class; Karp's 1972 paper demonstrated its breadth with 21 additional NP-complete problems.

NP-completeness is a worst-case property. It says that the hardest instances of an NP-complete problem require superpolynomial time on a deterministic machine. It does not say that typical instances are hard — many NP-complete problems are routinely solved in practice by heuristics, approximation algorithms, and SAT solvers that exploit the structure of real-world instances. The popular conflation of NP-completeness with practical intractability is a consistent misreading that misleads engineers and policymakers alike.