Computer science Computational complexity: resources and classes Concept
NP-completeness
Summary
A decision problem is NP-complete when it lies in NP and is NP-hard. The NP-complete problems are the hardest problems in NP: a polynomial-time algorithm for any one of them gives polynomial-time algorithms for all of NP. Thousands of natural problems are NP-complete, among them satisfiability, graph colouring, the Hamiltonian cycle problem and subset sum. So P equals NP exactly when some NP-complete problem lies in .
Where this leads
22 pages build on this one.
- Christofides algorithm
- Ladner's theorem
- Graph isomorphism problem
- Constraint satisfaction problem
- Knapsack problem
- Goemans–Williamson algorithm
- Cook–Levin theorem
- Facility location problem
- Quadratic assignment problem
- Subset sum problem
- Schaefer's dichotomy theorem
- Lin–Kernighan heuristic
- NP-hardness of integer programming
- P versus NP problem
- Polynomial-time submodular minimization
- Steiner tree problem
- Maximum cut
- Vehicle routing problem
- Travelling salesman problem
- Set cover problem
- Karp's 21 NP-complete problems
- Held–Karp algorithm
Further reading
About this page
| Tag | JGZWHWA8P8 |
|---|---|
| URI | m2://JGZWHWA8P8 |
| Kind | concept |
| Writing | W0 stub |
| MSC | 68Q17, 68Q15 |
| Specializes | NP-hardness |
| Same as | |
| Changed | 3 November 2026 |
Markdown · JSON · Edit on GitHub
What this page needs for W1
- a source with a locator (0 of 1)
The writing levels say how complete the text of a page is. They do not measure its truth.
What links here
Results about this
Used by
- Ladner's theorem
- Graph isomorphism problem
- Constraint satisfaction problem
- Knapsack problem
- Cook–Levin theorem
- Subset sum problem
- Schaefer's dichotomy theorem
- NP-hardness of integer programming
- P versus NP problem
- Steiner tree problem
- Maximum cut
- Travelling salesman problem
- Set cover problem