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.

Because there are decision problems that may or may not be undecidable due to the halting problem and the set of all Turing Machine's being higher than the amount of languages possible to process, it is impossible to solve all of these decision problems, but they are countably infinite

## External links[edit]

* Complexity Zoo: Class ALL

* v
* t
* e

Important complexity classes

Considered feasible|

* DLOGTIME
* AC0
* ACC0
* TC0
* L
* SL
* RL
* 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
* 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