Computer science Computational complexity: resources and classes Concept
NP
Summary
NP is the complexity class of decision problems whose "yes" answers can be checked in polynomial time with the help of a suitable certificate. Equivalently, it is the class of problems that a nondeterministic Turing machine solves in polynomial time. It contains P and many problems of practical interest, such as satisfiability, graph colouring and scheduling. Whether NP equals P is the central open question of complexity theory.
Where this leads
23 pages build on this one.
- Ladner's theorem
- Boolean satisfiability problem
- Graph isomorphism problem
- Constraint satisfaction problem
- Exponential time hypothesis
- Knapsack problem
- Polynomial hierarchy
- NP-hardness
- Baker–Gill–Solovay theorem
- Cook–Levin theorem
- Hardness of approximation
- Subset sum problem
- Schaefer's dichotomy theorem
- Karp–Lipton theorem
- NP-hardness of integer programming
- P versus NP problem
- co-NP
- NP-completeness
- EXPTIME
- PSPACE-completeness
- PCP theorem
- PSPACE
- Karp's 21 NP-complete problems
Further reading
About this page
| Tag | QQRA9GBW51 |
|---|---|
| URI | m2://QQRA9GBW51 |
| Kind | concept |
| Writing | W0 stub |
| MSC | 68Q15 |
| 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
- Boolean satisfiability problem
- Graph isomorphism problem
- Constraint satisfaction problem
- Polynomial hierarchy
- NP-hardness
- Baker–Gill–Solovay theorem
- Cook–Levin theorem
- Hardness of approximation
- Subset sum problem
- Karp–Lipton theorem
- P versus NP problem
- co-NP
- NP-completeness
- PSPACE-completeness
- PCP theorem
- PSPACE