thumb|right|A representation of the relation among complexity classes

This is a list of complexity classes in computational complexity theory. For other computational and complexity subjects, see list of computability and complexity topics.

Many of these classes have a 'co' partner which consists of the complements of all languages in the original class. For example, if a language L is in NP then the complement of L is in co-NP. (This does not mean that the complement of NP is co-NP—there are languages which are known to be in both, and other languages which are known to be in neither.)

"The hardest problems" of a class refer to problems which belong to the class such that every other problem of that class can be reduced to it.

{|

|#P||Count solutions to an NP problem

|-

|#P-complete||The hardest problems in #P

|-

|2-EXPTIME||Solvable in doubly exponential time

|-

|AC<sup>0</sup>||A circuit complexity class of bounded depth

|-

|ACC<sup>0</sup>||A circuit complexity class of bounded depth and counting gates

|-

|AC||A circuit complexity class

|-

|AH||The arithmetic hierarchy

|-

|AP||The class of problems alternating Turing machines can solve in polynomial time.

|-

|APX||Optimization problems that have approximation algorithms with constant approximation ratio

|-

|TFNP||Total function problems solvable in non-deterministic polynomial time. A problem in this class has the property that every input has an output whose validity may be checked efficiently, and the computational challenge is to find a valid output.

|-

|UP||Unambiguous Non-Deterministic Polytime functions.

|-

|ZPL||Solvable by randomized algorithms (answer is always right, average space usage is logarithmic)

|-

|ZPP||Solvable by randomized algorithms (answer is always right, average running time is polynomial)

|}

References

  • Complexity Zoo - list of over 500 complexity classes and their properties