# Other Complexity Classes

DevFeed: [Other Complexity Classes](<https://devfeed.tech/articles/other-complexity-classes-40264.md>)

Original publisher: [Read original article](<https://www.jeremykun.com/2012/02/29/other-complexity-classes/>)

Published: 2012-02-29T17:12:35Z

Content type: article

Language: en

Sources: [Jeremy Kun](<https://devfeed.tech/sources/jeremy-kun.md>)

Topics: [Algorithms, Complexity](<https://devfeed.tech/topics/algorithms-complexity.md>), [Computing](<https://devfeed.tech/topics/computing.md>), [Math and Logic](<https://devfeed.tech/topics/math-and-logic.md>)

Tags: [complexity](<https://devfeed.tech/tags/complexity.md>), [computational-complexity](<https://devfeed.tech/tags/computational-complexity.md>), [halting-problem](<https://devfeed.tech/tags/halting-problem.md>), [kolmogorov-complexity](<https://devfeed.tech/tags/kolmogorov-complexity.md>), [nondeterminism](<https://devfeed.tech/tags/nondeterminism.md>), [open-questions](<https://devfeed.tech/tags/open-questions.md>), [oracle](<https://devfeed.tech/tags/oracle.md>), [primer](<https://devfeed.tech/tags/primer.md>), [pspace](<https://devfeed.tech/tags/pspace.md>), [turing-machine](<https://devfeed.tech/tags/turing-machine.md>), [turing-machines](<https://devfeed.tech/tags/turing-machines.md>)

## AI overview

This article introduces complexity classes beyond P and NP, including PSPACE and NPSPACE, and discusses oracle-based classes. It explains that PSPACE equals NPSPACE while many relationships among complexity classes remain open.

## Source excerpt

Not Just Time, But Space Too! So far on this blog we've introduced models for computation, focused on Turing machines and given a short overview of the two most fundamental classes of problems: P and NP. While the most significant open question in the theory of computation is still whether P = NP, it turns out that there are hundreds (almost 500, in fact!) other "classes" of problems whose relationships are more or less unknown.