Template:Complexity classes

Template documentation[create]

Editors can experiment in this template's sandbox (create | mirror) and testcases (create) pages.
Please add categories to the /doc subpage. Subpages of this template.

v t e Complexity classes
Considered feasible	DLOGTIME AC⁰ ACC⁰ TC⁰ L SL RL FL NL NL-complete NC SC CC P P-complete ZPP RP BPP BQP APX FP
Suspected infeasible	NP NP-hard NP-complete co-NP co-NP-complete UP 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

Navigation menu