NP-Complete Problems
NP-complete problems are the hardest in NP: every NP problem reduces to them, so a fast solution to one would solve all of NP.
Two conditions
A problem is NP-complete if it satisfies two conditions: it is in NP, and every problem in NP reduces to it in polynomial time. The second condition makes it a hardest problem in the class, a universal target that captures the difficulty of all of NP.
The keystone: SAT
The Cook-Levin theorem proved that Boolean satisfiability is NP-complete, the first such result. Once one NP-complete problem is known, others are shown NP-complete by reducing SAT (or another known NP-complete problem) to them.
A gallery of examples
- 3-SAT: satisfiability with three literals per clause
- Traveling salesman (decision version)
- Graph coloring with three or more colors
- Subset sum and knapsack (decision version)
- Clique, vertex cover, and independent set
- Hamiltonian cycle
Why the class is remarkable
These problems come from logic, graphs, scheduling, and number theory, yet they are all equivalent in difficulty: solve any one efficiently and you solve them all. This unexpected unity is one of the deepest facts in computer science, tying thousands of practical problems to a single question.
The stakes
No polynomial-time algorithm is known for any NP-complete problem, and finding one would prove P equals NP. Proving none exists would settle the question the other way. Either resolution would reshape cryptography, optimization, and much of computing.
What to do in practice
Faced with an NP-complete problem, practitioners do not seek an exact fast solver. They use approximation, heuristics, exact solvers that are fast on typical instances, or restrictions of the problem that fall into P. Recognizing NP-completeness is a signal to change strategy, not to keep hunting for a perfect polynomial algorithm.