ALL (complexity)

In computability and complexity theory, ALL is the class of all decision problems.

## Relations to other classes

[edit]

ALL contains all of the complex classes of decision problems, including RE and co-RE, and uncountably many languages that are neither RE nor co-RE. It is the largest complexity class, containing all other complexity classes.

## External links

[edit]

* Complexity Zoo: Class ALL

* v
* t
* e

Complexity classes

Considered feasible|

* DLOGTIME
* AC0
* ACC0
* TC
* TC0
* L
* SL
* RL
* FL
* NL
* NL-complete
* NC
* SC
* CC
* P
* P-complete
* ZPP
* RP
* BPP
* BQP
* APX
* FP

Suspected infeasible|

* UP
* NP
* NP-complete
* NP-hard
* co-NP
* co-NP-complete
* TFNP
* FNP
* AM
* QMA
* PH
* ⊕P
* PP
* #P
* #P-complete
* IP
* PSPACE
* PSPACE-complete

Considered infeasible|

* EXPTIME
* NEXPTIME
* EXPSPACE
* 2-EXPTIME
* ELEMENTARY
* PR
* R
* RE
* ALL

Class hierarchies|

* Polynomial hierarchy
* Exponential hierarchy
* Grzegorczyk hierarchy
* Arithmetical hierarchy
* Boolean hierarchy

Families of classes|

* DTIME
* NTIME
* DSPACE
* NSPACE
* Probabilistically checkable proof
* Interactive proof system

List of complexity classes

P ≟ NP |

This theoretical computer science–related article is a stub. You can help Wikipedia by expanding it.

|

* v
* t
* e

*[v]: View this template
*[t]: Discuss this template
*[e]: Edit this template