ALL (complexity)

From Wikipedia, the free encyclopedia

Jump to: navigation, search

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

Relations to other classes[edit]

ALL contains all complexity classes of decision problems, including RE and co-RE.

External links[edit]

Complexity Zoo: Class ALL

v t e Important complexity classes (more)

Considered feasible	DLOGTIME AC⁰ ACC⁰ TC⁰ L SL RL NL NC SC CC P P-complete ZPP RP BPP BQP

Suspected infeasible	UP NP NP-complete NP-hard co-NP co-NP-complete AM PH ⊕P PP #P #P-complete IP PSPACE PSPACE-complete

Considered infeasible	EXPTIME NEXPTIME EXPSPACE ELEMENTARY PR R RE ALL

Class hierarchies	Polynomial hierarchy Exponential hierarchy Grzegorczyk hierarchy Arithmetic hierarchy Boolean hierarchy

Families of classes	DTIME NTIME DSPACE NSPACE Probabilistically checkable proof Interactive proof system

Retrieved from "http://en.wikipedia.org/w/index.php?title=ALL_(complexity)&oldid=543401631"

Complexity classes