Computer science Computational complexity: resources and classes Concept
Complexity class
Summary
A complexity class is a set of computational problems that can be solved within a given bound on some resource. The usual resources are time and space on a fixed model of computation, such as the Turing machine. Classes such as P, NP and PSPACE group problems by how hard they are to solve. The main questions of complexity theory are about inclusions between such classes.
Where this leads
16 pages build on this one.
Further reading
About this page
| Tag | ESPYW94XGR |
|---|---|
| URI | m2://ESPYW94XGR |
| Kind | concept |
| Writing | W0 stub |
| MSC | 68Q15 |
| Same as | |
| Changed | 3 November 2026 |
Markdown · JSON · Edit on GitHub
What this page needs for W1
- an inventory row: the row of the inventory that the node accounts for (0 of 1)
- 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
Special cases
Used by
- Complexity of computing a Nash equilibrium
- L
- RP
- BPP
- NL
- Interactive proof system
- co-NP
- P/poly
- Descriptive complexity theory
- NP
- Quantum complexity class BQP
- EXPTIME
- PCP theorem
- PSPACE
- ZPP
- P