# Complexity class

A complexity class is a set of computational problems, formalized as languages, that can all be decided by a fixed model of computation, such as a [Turing machine](https://www.edgepedia.org/turing-machine), within a stated bound on a resource such as running time or memory space.<sup>[1](https://plato.stanford.edu/archives/sum2024/entries/computational-complexity/)</sup> The field of computational complexity theory studies the relationships among these classes and between the classes and the problems they contain.<sup>[2](https://arxiv.org/abs/2009.04259)</sup>

| Key fact | Detail |
|---|---|
| Definition | Languages decidable within a given time or space bound \( t(n) \) or \( s(n) \) on a fixed model of computation<sup>[1](https://plato.stanford.edu/archives/sum2024/entries/computational-complexity/)</sup> |
| Core resources | Running time and memory space of an algorithm; DSPACE[f(n)] is the class of languages accepted by deterministic Turing machines with space bounded by f(n)<sup>[3](https://www.sciencedirect.com/topics/mathematics/complexity-space)</sup> |
| P and NP | P = DTIME(n^O(1)) and NP = NTIME(n^O(1)); P ⊆ NP, and the P versus NP question asks whether the inclusion is proper<sup>[4](https://citeseerx.ist.psu.edu/document?doi=4e29ef264c395eead5a9735c7d5f519d7d2ba094&repid=rep1&type=pdf)</sup> |
| NP-completeness | Cook (1971) showed SAT is hardest in NP; Karp extended the list; Levin proved a similar theorem independently<sup>[4](https://citeseerx.ist.psu.edu/document?doi=4e29ef264c395eead5a9735c7d5f519d7d2ba094&repid=rep1&type=pdf)</sup> |
| Known separations | Time Hierarchy Theorem: P ≠ EXP ≠ 2EXP; Space Hierarchy Theorem: L ≠ PSPACE ≠ EXPSPACE<sup>[5](https://courses.csail.mit.edu/6.892/spring19/lectures/L01.html)</sup> |
| Machine independence | Raw TIME(f) and SPACE(f) classes can depend on the exact Turing machine definition, but robust complexity classes do not<sup>[6](https://cs.uwaterloo.ca/~s4bendav/files/CS360S21Lec20.pdf)</sup> |
| Open status | P versus NP, formulated independently by Stephen Cook and Leonid Levin in 1971, is one of the Clay Mathematics Institute Millennium Prize Problems<sup>[7](https://www.claymath.org/millennium/p-vs-np/)</sup> |

## Formal definition

A complexity class collects the languages decidable within a given time or space bound with respect to a fixed model of computation. To avoid pathologies from unnatural bounds, such as non-recursive ones, the bounds are restricted to constructible functions: a function \( t(n) \) is time constructible if some Turing machine, on input \( 1^{n} \), halts after exactly \( t(n) \) steps.<sup>[1](https://plato.stanford.edu/archives/sum2024/entries/computational-complexity/)</sup> Equivalently, given a time-constructible \( f(n) \), TIME(\( f(n) \)) consists of all languages \( L \) for which some Turing machine decides \( L \) while always halting after at most \( O(f(n)) \) steps.<sup>[8](https://www.cs.yale.edu/homes/aspnes/classes/468/notes.pdf)</sup>

The same pattern defines space classes: SPACE(f) is the class of languages decidable by a Turing machine whose work space is bounded by f, and DSPACE(S(n)) is the class accepted by S(n) space-bounded deterministic machines.<sup>[6](https://cs.uwaterloo.ca/~s4bendav/files/CS360S21Lec20.pdf)</sup><sup> • </sup><sup>[9](https://www.comp.nus.edu.sg/~sanjay/cs5230/complex.pdf)</sup> In principle any function from natural numbers to natural numbers could serve as the bound, but the typical natural bounds such as 1, n, n log n, \( n^{3} \), and \( 2^{n} \) behave well, and constructibility is the formal way to delimit the functions used.<sup>[3](https://www.sciencedirect.com/topics/mathematics/complexity-space)</sup>

Time and space relate directly: a machine with time complexity \( f(n) \) cannot touch more than \( f(n) \) cells, so KTIME(\( f(n) \)) ⊆ KSPACE(\( f(n) \)).<sup>[10](https://planetmath.org/complexityclass)</sup>

## Major classes

The two central classes are defined by polynomial bounds under deterministic and nondeterministic computation. P = DTIME(n^O(1)) contains the problems time-tractable in the fundamental (deterministic) mode, and NP = NTIME(n^O(1)) contains those tractable in the nondeterministic mode; clearly P ⊆ NP.<sup>[4](https://citeseerx.ist.psu.edu/document?doi=4e29ef264c395eead5a9735c7d5f519d7d2ba094&repid=rep1&type=pdf)</sup> Informally, P holds the problems a classical deterministic computer solves in polynomial time, NP the problems whose solutions a deterministic classical computer can check in polynomial time, BPP those solvable by a classical probabilistic computer in polynomial time, [BQP](https://www.edgepedia.org/bqp) those solvable by a quantum computer in polynomial time, and [QMA](https://www.edgepedia.org/qma) those whose solutions a quantum computer can check in polynomial time.<sup>[11](https://ccet.acm.org/assets/2022%20JAN%20FEB-BF9YEDR9.pdf)</sup>

Beyond time-bounded classes, the standard catalog includes coNP, PSPACE, and more recent classes such as NC and #P, along with PO and NPO, which arise from the study of approximability of optimization problems. These correspond to three basic forms of computational task: decision problems, counting problems, and optimization problems.<sup>[12](https://epubs.siam.org/doi/book/10.1137/1.9780898718546)</sup> A standard course sequence also defines EXP, R, coNP, PSPACE, EXPSPACE, L, 2EXP, and 2EXPSPACE alongside P and NP.<sup>[5](https://courses.csail.mit.edu/6.892/spring19/lectures/L01.html)</sup>

## Completeness and reductions

Classes are compared through reductions, and the hardest problems in a class are its complete problems. In 1971 [Stephen Cook](https://www.edgepedia.org/stephen-cook) proved a theorem connecting P and NP by showing that recognizing satisfiable Boolean formulas is the hardest problem in NP, in the sense that if this problem is in P then P = NP. Shortly afterwards, Richard Karp showed that a large list of problems of practical importance in operations research and combinatorial optimization are also hardest in this sense, and [Leonid Levin](https://www.edgepedia.org/leonid-levin) independently proved a theorem similar to Cook's result.<sup>[4](https://citeseerx.ist.psu.edu/document?doi=4e29ef264c395eead5a9735c7d5f519d7d2ba094&repid=rep1&type=pdf)</sup> Cook and Levin formulated the [P versus NP problem](https://www.edgepedia.org/p-versus-np-problem) independently in 1971.<sup>[7](https://www.claymath.org/millennium/p-vs-np/)</sup>

The list of NP-hard problems has since grown to include hundreds of problems from practically every area of the computational literature, cataloged comprehensively up to 1979 by Garey and Johnson.<sup>[4](https://citeseerx.ist.psu.edu/document?doi=4e29ef264c395eead5a9735c7d5f519d7d2ba094&repid=rep1&type=pdf)</sup> Once a new problem is shown NP-complete, researchers usually stop expecting a generic exact polynomial-time algorithm for it unless P equals NP.<sup>[13](https://www.codehistory.org/algorithms-data-structures-computational-complexity/stephen-cook-leonid-levin-discovery-np-completeness/)</sup> The practical force of completeness is that a fast algorithm for any one complete problem translates into fast algorithms for all other problems in the class.<sup>[14](https://epubs.siam.org/doi/book/10.1137/1.9781611970395)</sup>

Completeness notions themselves differ. Under the hypothesis that NP does not have p-measure 0, there exists a language that is Cook-complete for NP under Turing reductions but not Karp-Levin-complete under many-one reductions.<sup>[15](https://www.sciencedirect.com/science/article/pii/0304397595001891)</sup>

## Hierarchy theorems and machine independence

Some separations between classes are proved. Savitch's theorem gives NPSPACE = PSPACE, the Time Hierarchy Theorem gives P ≠ EXP ≠ 2EXP, and the Space Hierarchy Theorem gives L ≠ PSPACE ≠ EXPSPACE.<sup>[5](https://courses.csail.mit.edu/6.892/spring19/lectures/L01.html)</sup> These hierarchy results show that granting more of a resource strictly enlarges what can be computed.

The raw classes TIME(f) and SPACE(f) depend on the exact definition of a Turing machine, but robust complexity classes do not depend on those details.<sup>[6](https://cs.uwaterloo.ca/~s4bendav/files/CS360S21Lec20.pdf)</sup> This robustness is what lets results such as the P versus NP question be stated about problems rather than about one particular machine model.<sup>[16](https://www.calculemus.org/lect/L-I-MNS/12/computComplexity/NP-cook.html)</sup>

## P versus NP

The P versus NP question asks whether the inclusion P ⊆ NP is proper.<sup>[4](https://citeseerx.ist.psu.edu/document?doi=4e29ef264c395eead5a9735c7d5f519d7d2ba094&repid=rep1&type=pdf)</sup> It is one of the seven [Millennium Prize Problems](https://www.edgepedia.org/millennium-prize-problems) stated by the [Clay Mathematics Institute](https://www.edgepedia.org/clay-mathematics-institute) in 2000, and its official problem description was written by Stephen Cook.<sup>[7](https://www.claymath.org/millennium/p-vs-np/)</sup><sup> • </sup><sup>[17](https://jntukucev.hosting2.acm.org/2023/02/01/overview-of-theory-of-computation/)</sup> Most researchers believe that P is not equal to NP, and because of this belief a proof that a problem is hardest for NP is taken as strong evidence that the problem is not in P.<sup>[4](https://citeseerx.ist.psu.edu/document?doi=4e29ef264c395eead5a9735c7d5f519d7d2ba094&repid=rep1&type=pdf)</sup>

The question connects to other class relationships. By a theorem of Cook and Reckhow (1979), a polynomially bounded proof system exists if and only if NP = coNP.<sup>[1](https://plato.stanford.edu/archives/sum2024/entries/computational-complexity/)</sup> The importance of the question also stems from the theories of [NP-completeness](https://www.edgepedia.org/np-completeness) and complexity-based cryptography built on it, as well as the practical consequences a constructive proof of P = NP would have.<sup>[18](https://www.claymath.org/wp-content/uploads/2022/02/MPPc.pdf)</sup>

## References

1. [Computational Complexity Theory, Stanford Encyclopedia of Philosophy (Summer 2024)](https://plato.stanford.edu/archives/sum2024/entries/computational-complexity/)
2. [Completeness in Polylogarithmic Time and Space, arXiv:2009.04259](https://arxiv.org/abs/2009.04259)
3. [Complexity Space, ScienceDirect Topics](https://www.sciencedirect.com/topics/mathematics/complexity-space)
4. [Theory of Complexity Classes, Chapter 3: Introduction to the Class NP, CiteSeerX](https://citeseerx.ist.psu.edu/document?doi=4e29ef264c395eead5a9735c7d5f519d7d2ba094&repid=rep1&type=pdf)
5. [Lecture 1, 6.892 Algorithmic Lower Bounds, MIT CSAIL (Spring 2019)](https://courses.csail.mit.edu/6.892/spring19/lectures/L01.html)
6. [CS 360 Lecture 20: Resource-Bounded Computations, University of Waterloo](https://cs.uwaterloo.ca/~s4bendav/files/CS360S21Lec20.pdf)
7. [P vs NP, Clay Mathematics Institute](https://www.claymath.org/millennium/p-vs-np/)
8. [Notes on Computational Complexity, Yale University (Aspnes)](https://www.cs.yale.edu/homes/aspnes/classes/468/notes.pdf)
9. [Complexity notions lecture notes, National University of Singapore](https://www.comp.nus.edu.sg/~sanjay/cs5230/complex.pdf)
10. [Complexity class, PlanetMath](https://planetmath.org/complexityclass)
11. [CCET ACM Student Chapter Tech Magazine, Vol. 2, Issue 3 (2022)](https://ccet.acm.org/assets/2022%20JAN%20FEB-BF9YEDR9.pdf)
12. [Complexity Classifications of Boolean Constraint Satisfaction Problems, SIAM](https://epubs.siam.org/doi/book/10.1137/1.9780898718546)
13. [Cook, Levin and the Discovery of NP-Completeness, CodeHistory](https://www.codehistory.org/algorithms-data-structures-computational-complexity/stephen-cook-leonid-levin-discovery-np-completeness/)
14. [Feasible Computations and Provable Complexity Properties, SIAM Publications](https://epubs.siam.org/doi/book/10.1137/1.9781611970395)
15. [Cook versus Karp-Levin: Separating completeness notions if NP is not small, Theoretical Computer Science](https://www.sciencedirect.com/science/article/pii/0304397595001891)
16. [The P versus NP Problem, Calculemus lecture notes](https://www.calculemus.org/lect/L-I-MNS/12/computComplexity/NP-cook.html)
17. [Overview of Theory of Computation, ACM Student Branch JNTUGV CEV](https://jntukucev.hosting2.acm.org/2023/02/01/overview-of-theory-of-computation/)
18. [The P Versus NP Problem, Clay Mathematics Institute (Millennium Prize Problems description)](https://www.claymath.org/wp-content/uploads/2022/02/MPPc.pdf)

---
*Topic: Encyclopedia › Technology and the built world › Computing and digital systems › Artificial intelligence and data › Algorithms and computational methods › Computational complexity › Classical complexity classes*

*Initially written Sep 17, 2026 · Reviewed: Oct 15, 2026 · Edited: Oct 15, 2026 · Last review: Oct 15, 2026*

*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*

License: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license