NP-Completeness
An NP-complete problem is one that is both in NP and NP-hard, meaning every NP problem reduces to it in polynomial time. All NP-complete problems are interreducible, so an efficient algorithm for any one would solve them all and prove P = NP.
A decision problem is **NP-complete** when it satisfies two conditions: 1. it is in NP (a candidate solution is verifiable in polynomial time), and 2. it is **NP-hard**: every problem in NP reduces to it via a polynomial-time reduction. ## The same problem in disguise Because all NP-complete problems are interreducible, they are equivalent under polynomial-time reduction — the same computational challenge wearing different surface forms. Solve one efficiently and you solve them all: just translate, solve, and translate back. (See The Sudoku-to-SAT Reduction: How to Translate One Problem Into Another.) ## The critical consequence If any single NP-complete problem had a polynomial-time algorithm, then every problem in NP would too, which would mean P = NP — resolving P versus NP. Conversely, if P ≠ NP, then no NP-complete problem is efficiently solvable. This is why these problems are the natural focus of the open question. ## How the class was bootstrapped The Cook–Levin theorem established the first NP-complete problem, SAT. Richard Karp's 1972 paper then proved 21 further problems NP-complete by chains of reductions, showing the class is large and diverse. ## Notable examples SAT, 3-SAT, the decision version of the travelling salesman problem, graph coloring, the knapsack problem, Hamiltonian path problem, vertex cover, the clique problem, and subset sum problem.