-
Notifications
You must be signed in to change notification settings - Fork 0
/
complexity.poset
123 lines (123 loc) · 2.21 KB
/
complexity.poset
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
# http://www.nomachetejuggling.com/files/complexity_zoo.pdf
# 1 Intro
P ≤ NP
# 2 DTIME and NTIME
DTIME(1) ≤ DLOGTIME ≤ TIME ≤ P
P ≤ EXPTIME ≤ ALL
NP ≤ NEXPTIME ≤ ALL
# 3 PP and BPP
BPP ≤ coBPP ≤ BPP
BPP ≤ PP ≤ ALL
P ≤ BPP
# 4 RP, coRP, and ZPP
P ≤ ZPP
ZPP ≤ RP ≤ NP
ZPP ≤ coRP ≤ coNP
# 5 MA and AM
NP ≤ MA
BPP ≤ MA
MA ≤ PP
MA ≤ AM
MA ≤ MAexp
AM ≤ AMexp
MAexp ≤ AMexp ≤ ALL
# 6 P/poly
P ≤ P/poly
BPP ≤ P/poly
# NC and AC
NC ≤ AC ≤ NC
AC0 ≤ AC
NC1 ≤ NC
# 8 BQP and QMA
P ≤ BPP ≤ BQP ≤ PP
P ≤ NP ≤ MA ≤ QMA ≤ PP
# 9 PH
P ≤ PH
NP ≤ PH
coNP ≤ PH
PH ≤ PSPACE
# https://complexityzoo.uwaterloo.ca/File:Really-important-inclusions.png
AC0 ≤ L ≤ NC
P/poly ≤ ALL
P^#P ≤ PSPACE ≤ EXP ≤ ALL
# Petting Zoo
# NP
NP-complete ≤ NP
coNP-complete ≤ coNP
# PSPACE
NP ≤ PSPACE
PP ≤ PSPACE
PSPACE ≤ PSPACE/poly
# EXP
PSPACE ≤ EXP
PH ≤ EXP
EXP ≤ NEXP ≤ ALL
EXP ≤ EEXP ≤ ALL
# AC0
NC0 ≤ AC0
# NC
NC0 ≤ NC1
NC ≤ P
# L
NC1 ≤ L ≤ P
L ≤ NL
L ≤ SL ≤ L
L ≤ L/poly
# #P
PH ≤ P^#P
# BPP
BPP ≤ SZK ≤ AM
BPP ≤ BPPpath
MA ≤ BPPpath ≤ PP
# Savitch's Theorem
NPSPACE ≤ PSPACE ≤ NPSPACE
# ALL
PP ≤ ALL ≤ PP/rpoly ≤ ALL
PostBQP ≤ ALL ≤ PostBQP/qpoly ≤ ALL
QIP ≤ ALL ≤ QIP/qpoly ≤ ALL
MAexp ≤ ALL ≤ MAexp/rpoly ≤ ALL
# IP
IP ≤ PSPACE ≤ IP
# MIP
MIP ≤ NEXP ≤ MIP
# QIP
IP ≤ QIP ≤ IP
QIP(0) ≤ QIP(1) ≤ QIP(2) ≤ QIP(3) ≤ QIP ≤ QIP(3)
QIP ≤ EXP
BQP ≤ QIP(0) ≤ BQP
QMA ≤ QIP(1) ≤ QMA
# QMA
BQP ≤ QMA ≤ PP
QMA ≤ QMA/qpoly ≤ PSPACE/poly ≤ ALL
# PostBQP
PP ≤ PostBQP ≤ PP
# PR
EXP ≤ ELEMENTARY ≤ PR ≤ R
# TALLY
TALLY ≤ SPARSE ≤ ALL
# SZK
PZK ≤ SZK ≤ CZK ≤ ALL
# NC
# https://en.wikipedia.org/wiki/NC_(complexity)
NC1 ≤ NC2 ≤ NC
NC1 ≤ L ≤ NL ≤ AC1 ≤ NC2 ≤ P
# R
R ≤ RE ≤ ALL
R ≤ coRE ≤ ALL
# REG
REG ≤ DSPACE ≤ REG ≤ NC1
# TC0
ACC0 ≤ TC0 ≤ NC1
# WP's listing of "Important Complexity Classes"
# RL
L ≤ RL ≤ NL
RL ≤ BPL
RL ≤ SC ≤ ALL
# CC
NL ≤ CC ≤ P
# APX
FPTAS ≤ PTAS ≤ APX ≤ NPO
# Time & Space Hierarchy basics
P ≤ NP ≤ PSPACE ≤ EXPTIME ≤ NEXPTIME ≤ EXPSPACE ≤ ALL
# EXP = EXPTIME
EXP ≤ EXPTIME ≤ EXP