NP-Completeness
NP-completeness is a classification in computational complexity theory denoting decision problems that are both in NP (solutions verifiable in polynomial time) and NP-hard (at least as hard as every problem in NP under polynomial-time reductions). A problem is NP-complete if every NP problem can be transformed into it in polynomial time, implying that finding a polynomial-time algorithm for any one NP-complete problem would solve all NP problems. Classic NP-complete problems include Boolean satisfiability (SAT), the Travelling Salesman Problem (decision version), and the Subset Sum problem.
Classic NP-Complete Problems and Their Real-World Applications
| Problem | Input | Question | Real-World Application | Best Known Complexity |
|---|---|---|---|---|
| Boolean SAT | Propositional formula | Is there a satisfying assignment? | Circuit design, software verification | O(2^n) worst case |
| Travelling Salesman (decision) | Cities, distances, bound k | Tour of cost ≤ k? | Logistics, chip manufacturing | O(n! ) exact |
| Knapsack (0/1) | Items with weights/values, capacity | Value ≥ k within capacity? | Resource allocation, budgeting | O(2^n) exact |
| Graph Colouring (k≥3) | Graph G, integer k | Colourable with k colours? | Register allocation, scheduling | O(k^n) exact |
| Subset Sum | Set of integers, target T | Subset summing to T? | Cryptography, financial planning | O(2^n) exact |
| Hamiltonian Path | Graph G | Path visiting all vertices once? | DNA sequencing, network design | O(n! ) exact |
Interactive Tools
Wikimedia Commons, CC BY-SA
Related Terms
P vs NP Problem
The P vs NP problem asks whether every problem whose solution can be verified in polynomial time (class NP) can also be solved in polynomial time (class P). It is one of the seven Millennium Prize Problems, carrying a $1,000,000 prize from the Clay Mathematics Institute, and is considered the most important open question in theoretical computer science. If P = NP were proven, it would imply that problems like RSA encryption, protein folding optimisation, and NP-complete combinatorial problems could all be solved efficiently, fundamentally transforming cryptography, artificial intelligence, and computational biology.
Dynamic Programming
Dynamic Programming (DP) is an algorithmic paradigm that solves complex problems by breaking them into overlapping subproblems, solving each subproblem only once, and storing results to avoid redundant computation (memoization or tabulation). It applies when a problem exhibits two key properties: optimal substructure (optimal solution contains optimal solutions to subproblems) and overlapping subproblems. DP is used in sequence alignment, shortest-path problems, knapsack optimization, and compiler design.
The term "NP-complete" was coined by Stephen Cook in his landmark 1971 paper "The Complexity of Theorem Proving Procedures," where he proved SAT is NP-complete. "NP" stands for "Nondeterministic Polynomial time," referring to nondeterministic Turing machines. Richard Karp extended the framework in 1972 by demonstrating 21 additional NP-complete problems.