Template:Complexity classes - Simple English Wikipedia, the free encyclopedia

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