Jump to content
Main menu
Main menu
move to sidebar
hide
Getting around
Main page
Simple start
Simple talk
New changes
Show any page
Help
Contact us
Give to Wikipedia
About Wikipedia
Search
Appearance
Create account
Log in
Personal tools
Create account
Log in
Pages for logged out editors
learn more
Contributions
Talk
Template
:
Complexity classes
15 languages
العربية
Bosanski
Català
English
فارسی
Français
한국어
Hrvatski
日本語
Polski
Português
Русский
Українська
Tiếng Việt
中文
Change links
Template
Talk
English
Read
Change source
View history
Tools
Tools
move to sidebar
hide
Actions
Read
Change source
View history
General
What links here
Related changes
Upload file
Special pages
Permanent link
Page information
Get shortened URL
Download QR code
Wikidata item
Print/export
Download as PDF
Page for printing
Appearance
move to sidebar
hide
From Simple English Wikipedia, the free encyclopedia
v
t
e
Complexity classes
Considered feasible
DLOGTIME
AC
0
ACC
0
TC
0
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
Template documentation
[
create
] [
purge
]
Editors can experiment in this template's sandbox
(
create
|
mirror
)
and testcases
(
create
)
pages.
Add categories to the
/doc
subpage.
Subpages of this template
.
Category
:
Computer science navigational boxes