Complexity Class Relations

This is a compilation of the relativizing inclusions and oracle separations which are the sharpest with respect to transitivity of inclusions. Where it says "∃X", it can be a different oracle X for each assertion on the right.

Citation information is incomplete on this page. The raw data has much better citations; one problem is that following all of the robozoologist's inferences leads too many citations.

See also:

Basic statistics: 394 classes (with co and cocap), 43653 inclusions, 92210 separations, 240 open cases, 18739 blank cases


(k>=5)-PBP: Polynomial-Size Width-k Branching Program for k>=5

Best inclusions: [Bar89]
∀X: 4-PBPX, MAJORITYX(k>=5)-PBPXNC^1X, PBPX
Best separations:
∃X: (k>=5)-PBPXPL_{infty}X
Likeliest blank:
∀X: (k>=5)-PBPX? TC^0/polyX
Blank case count: 16 ⊆? (k>=5)-PBPX? 27

(NP-cap-coNP)/poly: Nonuniform NP cap coNP

(NP-cap-coNP)/poly in the Zoo.

Best inclusions:
∀X: P/polyX, cocap.NPX(NP-cap-coNP)/polyXcocap.NP/polyX
Best separations: [FFK+93]
∃X: cocap.NP/oneX(NP-cap-coNP)/polyX
Likeliest blank:
∀X: PZKX, cocap.N.BPPX, cocap.NISZKX, cocap.WAPPX? (NP-cap-coNP)/polyX
Likeliest open:
∀X: cocap.PZKX? (NP-cap-coNP)/polyX
Unlikeliest blank:
∀X: BQP/qpolyX, DQPX, cocap.N.NISZKX, cocap.QMIPX, cocap.QMIP_{le}X, cocap.QMIP_{ne}X? (NP-cap-coNP)/polyX
Unlikeliest open:
∀X: cocap.PZKX? (NP-cap-coNP)/polyX
Blank case count: 79 ⊆? (NP-cap-coNP)/polyX? 6

+EXP: Parity EXP

+EXP in the Zoo.

Best inclusions:
∀X: EXPX, UEX+EXPXEXPSPACEX
Best separations: [BBF98]
∃X: BPQPX, ZPEX+EXPXBPEEX, NEEX, NEXP/polyX, SEHX
Likeliest blank:
∀X: Almost-PSPACEX, CheckX, QRGX, cocap.QMA(2)X, cocap.XOR-MIP*[2,1]X? +EXPX? EXPHX, PEXPX
Unlikeliest blank:
∀X: +EXPX? EXP^{NP}X, PEXPX
Blank case count: 27 ⊆? +EXPX? 6

+L: Parity L

+L in the Zoo.

Best inclusions: [GW96] [CKS81]
∀X: SPLX+LX+L/polyX, +SAC^1X, ALX
Likeliest blank:
∀X: cocap.R_HLX? +LX? AC^1X, L^{DET}X
Blank case count: 40 ⊆? +LX? 49

+L/poly: Nonuniform +L

+L/poly in the Zoo.

Best inclusions: [GW96]
∀X: +LX, NL/polyX+L/polyXP/polyX
Likeliest blank:
∀X: DCFLX, FOLLX, cocap.C_=LX? +L/polyX
Blank case count: 94 ⊆? +L/polyX? 13

+P: Parity P

+P in the Zoo.

Best inclusions: [GHJ+91]
∀X: NT*X, SPPX+PXModPX, SF_2X
Best separations:
∃X: Mod_3PX, Mod_5PX, ZPPX, compNPX+PX
Likeliest blank:
∀X: cocap.HalfPX? +PX
Unlikeliest blank:
∀X: +PX? NT*X
Blank case count: 41 ⊆? +PX? 10

+SAC^0: AC^0 With Unbounded Parity Gates

+SAC^0 in the Zoo.

Best inclusions: [Moo99]
∀X: NC^0X, PARITYX+SAC^0XAC^0[2]X, QNC_f^0X
Best separations:
∃X: +SAC^0XCSLX, PL_{infty}X, QCFLX
Unlikeliest blank:
∀X: AC^0[2]X, LINX, QAC^0X, QNC_f^0X? +SAC^0X
Blank case count: 12 ⊆? +SAC^0X? 12

+SAC^1: AC^1 With Unbounded Parity Gates

+SAC^1 in the Zoo.

Best inclusions: [GW96] [GW96]
∀X: +LX, SAC^1X+SAC^1XNC^2X
Likeliest blank:
∀X: BPLX, FOLLX, cocap.C_=LX? +SAC^1X
Unlikeliest blank:
∀X: +SAC^1X? ACC^0X, cocap.1NAuxPDA^pX
Blank case count: 21 ⊆? +SAC^1X? 52

1NAuxPDA^p: One-Way NAuxPDA^p [Bra77]

1NAuxPDA^p in the Zoo.

Best inclusions: [Bra77] [Bra77]
∀X: CFLX1NAuxPDA^pXSAC^1X
Likeliest blank:
∀X: 2-PBPX, NC^0X, co.CFLX, cocap.GCSLX? 1NAuxPDA^pX
∀X: cocap.1NAuxPDA^pX? CSLX, QX, QCFLX
Unlikeliest blank:
∀X: 1NAuxPDA^pX? 3-PBPX, LINX, cocap.CFLX
∀X: +SAC^1X, AC^1X, ALX, LINX, QCFLX, QNC^1X, SCX? cocap.1NAuxPDA^pX? DCFLX
Blank case count: 130 ⊆? 1NAuxPDA^pX? 127

2-PBP: Polynomial-Size Width-2 Branching Program

Best inclusions:
∀X: PARITYX2-PBPX3-PBPX, AC^0[2]X
Best separations:
∃X: NC^0X, REGX2-PBPX
Likeliest blank:
∀X: 2-PBPX? 1NAuxPDA^pX, PL_{infty}X, QX, QCFLX, QNC_f^0X
Unlikeliest blank:
∀X: 2-PBPX? PARITYX
Blank case count: 0 ⊆? 2-PBPX? 27

3-PBP: Polynomial-Size Width-3 Branching Program

Best inclusions:
∀X: 2-PBPX3-PBPX4-PBPX
Best separations:
∃X: 3-PBPXAC^0[2]X
Likeliest open:
∀X: 4-PBPX? 3-PBPX
Unlikeliest blank:
∀X: 1NAuxPDA^pX, GCSLX, PBPX, QCFLX, QNC^0X, cocap.SAC^0X? 3-PBPX
Unlikeliest open:
∀X: 4-PBPX? 3-PBPX
Blank case count: 18 ⊆? 3-PBPX? 25

4-PBP: Polynomial-Size Width-4 Branching Program

Best inclusions: [BT88]
∀X: 3-PBPX4-PBPX(k>=5)-PBPX, ACC^0X
Likeliest open:
∀X: 4-PBPX? 3-PBPX
Unlikeliest blank:
∀X: 4-PBPX? PL_1X, REGX
Unlikeliest open:
∀X: 4-PBPX? 3-PBPX
Blank case count: 18 ⊆? 4-PBPX? 25

A_0PP: One-Sided Analog of AWPP [Vya03]

A_0PP in the Zoo.

Best inclusions: [Vya03] [Vya03]
∀X: QMAX, co.C_=PXA_0PPXPPX
∀X: AWPPX, EPXcocap.A_0PPX
Likeliest blank:
∀X: APPX, C_=PX, co.NLINX, co.beta_2PX, co.compNPX, cocap.SBPX, cocap.USX? A_0PPX
Unlikeliest blank:
∀X: A_0PPX? BPP_{path}X, co.C_=PX, cocap.RP^{PromiseUP}X
∀X: cocap.A_0PPX? cocap.C_=PX
Blank case count: 152 ⊆? A_0PPX? 56

AC^0: Unbounded Fanin Constant-Depth Circuits

AC^0 in the Zoo.

Best inclusions:
∀X: SAC^0XAC^0XAC^0/polyX, AC^0[2]X, FOLLX, MAC^0X, QAC^0X
Best separations: [BS90] [BKL+00]
∃X: FOLLXAC^0XPL_{infty}X
Unlikeliest blank:
∀X: QAC^0X? AC^0X
Blank case count: 2 ⊆? AC^0X? 12

AC^0/poly: Nonuniform AC^0

Best inclusions:
∀X: AC^0X, SPARSEXAC^0/polyXTC^0/polyX
Likeliest blank:
∀X: FOLLX, MAJORITYX, PARITYX? AC^0/polyX? Nearly-PX
Unlikeliest blank:
∀X: AVBPPX, AmpP-BQPX, CSLX, CZKX, FHX, P-SelX, P/polyX, QX, QCFLX, QNCX, RBQPX, WAPPX, XOR-MIP*[2,1]X, cocap.betaPX, cocap.frIPX? AC^0/polyX
Blank case count: 136 ⊆? AC^0/polyX? 10

AC^0[2]: AC^0 With Parity Gates

Best inclusions:
∀X: +SAC^0X, 2-PBPX, AC^0XAC^0[2]XACC^0X
Best separations: [Raz87]
∃X: 3-PBPX, MAJORITYXAC^0[2]X
Unlikeliest blank:
∀X: AC^0[2]X? +SAC^0X
Blank case count: 6 ⊆? AC^0[2]X? 14

AC^1: Unbounded Fanin Log-Depth Circuits

AC^1 in the Zoo.

Best inclusions:
∀X: FOLLX, SAC^1XAC^1XNC^2X
Best separations: [Mil92]
∃X: NC^2XAC^1XNC^1X
Likeliest blank:
∀X: +LX, BPLX, cocap.C_=LX? AC^1X
Likeliest open:
∀X: SPLX? AC^1X
Unlikeliest blank:
∀X: AC^1X? LX, cocap.1NAuxPDA^pX
Unlikeliest open:
∀X: SPLX? AC^1X
Blank case count: 20 ⊆? AC^1X? 49

ACC^0: AC^0 With Arbitrary MOD Gates

ACC^0 in the Zoo.

Best inclusions: [BT88]
∀X: 4-PBPX, AC^0[2]XACC^0XQACC^0X, TC^0X
Unlikeliest blank:
∀X: +SAC^1X, ALX, QNC^1X, SCX? ACC^0X
Blank case count: 55 ⊆? ACC^0X? 13

AH: Arithmetic Hierarchy

AH in the Zoo.

Best inclusions:
∀X: REXAHXALLX
Best separations:
∃X: CohX, P-SelX, P/logX, TALLYXAHX
Likeliest blank:
∀X: cocap.MIP*X? AHX
Blank case count: 6 ⊆? AHX? 0

AL: Alternating L

AL in the Zoo.

Best inclusions: [CKS81] [CKS81] [CKS81]
∀X: +LX, L^{DET}XALXPX
Likeliest blank:
∀X: DCFLX, FOLLX? ALX? NLINSPACEX, QNCX
Unlikeliest blank:
∀X: HalfPX, QNCX? ALX? ACC^0X, cocap.1NAuxPDA^pX
Blank case count: 35 ⊆? ALX? 60

ALL: The Class of All Languages

ALL in the Zoo.

Best inclusions:
∀X: AHX, CohX, NEXP/polyX, Nearly-PX, P-SelX, PL_{infty}X, QMIPXALLX
Blank case count: 0 ⊆? ALLX? 0

Almost-PSPACE: Languages Almost Surely in PSPACE^A

Almost-PSPACE in the Zoo.

Best inclusions:
∀X: PSPACEXAlmost-PSPACEXBPEXPX
Best separations:
∃X: AvgPX, QPLINXAlmost-PSPACEX
Likeliest blank:
∀X: AVBPPX, QS_2PX, RGX, cocap.QIP[2]X? Almost-PSPACEX? +EXPX, EXP^{NP}X, NEEX, NEXP/polyX, SEHX
Likeliest open:
∀X: DQPX? Almost-PSPACEX
Unlikeliest blank:
∀X: Almost-PSPACEX? BP.PPX, EHX, ModPX, P-SelX, P^{QMA}X, RG[1]X, SF_2X
Unlikeliest open:
∀X: DQPX? Almost-PSPACEX
Blank case count: 36 ⊆? Almost-PSPACEX? 37

AM: Arthur-Merlin [BM88]

AM in the Zoo.

Best inclusions: [BM88] [BM88] [BGM02]
∀X: SBPXAMXAM[polylog]X, BPP^{NP}X, NP/polyX, QAMX, co.Sigma_2PX
∀X: SZKXcocap.AMXZPP^{NP}X
Best separations: [AGH90] [Ver92]
∃X: AM[polylog]XAMX
∃X: cocap.AMXPPX
Unlikeliest blank:
∀X: QIP[2]X? AMX
∀X: cocap.QMIPX, cocap.QMIP_{le}X, cocap.QMIP_{ne}X? cocap.AMX
Blank case count: 109 ⊆? AMX? 54

AM[polylog]: AM With Polylog Rounds

AM[polylog] in the Zoo.

Best inclusions:
∀X: AMXAM[polylog]XIPX
Best separations: [AGH90] [AGH90]
∃X: IPXAM[polylog]XAMX
Likeliest blank:
∀X: cocap.CZKX, cocap.compIPX? AM[polylog]X
∀X: cocap.AM[polylog]X? CHX, EHX, NE/polyX, PP/polyX, QIP[2]X
Unlikeliest blank:
∀X: NT*X, WAPPX, frIPX? cocap.AM[polylog]X
Blank case count: 129 ⊆? AM[polylog]X? 106

AM_{EXP}: Exponential-Time AM

AM_{EXP} in the Zoo.

Best inclusions:
∀X: MA_{EXP}XAM_{EXP}XIP_{EXP}X, co.NEXP^{NP}X
Best separations: [Ver92]
∃X: cocap.AM_{EXP}XPEXPX
Likeliest blank:
∀X: AM_{EXP}X? NEXP^{NP}X
Unlikeliest blank:
∀X: MIP_{EXP}X? AM_{EXP}X
∀X: cocap.MIP_{EXP}X? cocap.AM_{EXP}X
Blank case count: 36 ⊆? AM_{EXP}X? 6

AmpMP: Amplifiable MP [GKR+95]

AmpMP in the Zoo.

Best inclusions: [KT96]
∀X: ModPXAmpMPXMPX
Likeliest blank:
∀X: cocap.NLINX, cocap.RNCX, cocap.beta_2PX, cocap.compNPX? AmpMPX? ModPX
Blank case count: 190 ⊆? AmpMPX? 13

AmpP-BQP: BQP Restricted To AmpP States

AmpP-BQP in the Zoo.

Best inclusions:
∀X: TreeBQPXAmpP-BQPXBQPX, cocap.Sigma_3PX
Likeliest blank:
∀X: ZBQPX? AmpP-BQPX
Likeliest open:
∀X: AmpP-BQPX? TreeBQPX
Unlikeliest blank:
∀X: AmpP-BQPX? AC^0/polyX, BPPX, IC[log,poly]X, P-CloseX, YPPX, cocap.compIPX
Unlikeliest open:
∀X: AmpP-BQPX? TreeBQPX
Blank case count: 36 ⊆? AmpP-BQPX? 105

APP: Amplified PP [Li93]

APP in the Zoo.

Best inclusions: [Fen02]
∀X: AWPPXAPPXPPX
Likeliest blank:
∀X: YPX, cocap.EPX, cocap.NLINX, cocap.beta_2PX, cocap.compNPX? APPX? A_0PPX
Unlikeliest blank:
∀X: APPX? BPP_{path}X, cocap.C_=PX, cocap.RP^{PromiseUP}X
Blank case count: 99 ⊆? APPX? 30

AVBPP: Average-Case BPP [OW93]

AVBPP in the Zoo.

Best inclusions:
∀X: BPPXAVBPPXHeurBPPX
Best separations:
∃X: AvgPXAVBPPX
Likeliest blank:
∀X: AVBPPX? Almost-PSPACEX, CohX, DQPX, ESPACEX, NE/polyX, PP/polyX, QMIPX, QMIP_{le}X, QMIP_{ne}X, QRGX
Unlikeliest blank:
∀X: CZKX, DQPX, NLINSPACEX, NT*X, QX, QSZKX, SUBEXPX, WAPPX, YQPX, frIPX? AVBPPX? AC^0/polyX, BPPX, IC[log,poly]X, ModPX, P-CloseX, P-SelX, QAC^0X, QNC_f^0X, SF_2X, YPPX, ZQPX, cocap.C_=PX, cocap.NP/oneX, cocap.RP^{PromiseUP}X, cocap.compIPX
Blank case count: 77 ⊆? AVBPPX? 187

AvgE: Average Exponential-Time With Linear Exponent

AvgE in the Zoo.

Best inclusions:
∀X: EXAvgEXEEX
Best separations:
∃X: cocap.UPXAvgEXEXPSPACEX, MIP_{EXP}X, NEXP/polyX
Likeliest blank:
∀X: NT*X, QAC^0X, QCFLX, QNC^0X, cocap.HalfPX, cocap.RNCX, cocap.compNPX? AvgEX
Unlikeliest blank:
∀X: BPEX, CZKX, DQPX, HeurBPPX, QSZKX, WAPPX, XOR-MIP*[2,1]X, YQPX, frIPX? AvgEX
Blank case count: 73 ⊆? AvgEX? 0

AvgP: Average Polynomial-Time [Lev86]

AvgP in the Zoo.

Best inclusions:
∀X: PXAvgPXEX, HeurBPPX, Nearly-PX
Best separations:
∃X: AvgPXAVBPPX, Almost-PSPACEX, DQPX, P-SelX, PP/polyX, QMIPX, QMIP_{le}X, QMIP_{ne}X, QPSPACEX, QRGX, SUBEXPX
Likeliest blank:
∀X: AvgPX? CohX
Unlikeliest blank:
∀X: EQPX, NT*X, compIPX, polyLX? AvgPX
Blank case count: 26 ⊆? AvgPX? 1

AWPP: Almost WPP [FFK94]

AWPP in the Zoo.

Best inclusions: [Fen02] [FR98] [BGM02]
∀X: BQPX, WAPPX, WPPXAWPPXAPPX, cocap.A_0PPX
Unlikeliest blank:
∀X: PPX, P^{NP[log^2]}X, RP^{PromiseUP}X? AWPPX
Blank case count: 100 ⊆? AWPPX? 26

beta_2P: Log-Squared Nondeterminism NP [KF84]

Best inclusions:
∀X: beta_2PXQPLINX, betaPX
∀X: PXcocap.beta_2PX
Best separations: [Imp..]
∃X: beta_2PXco.NP/polyX, co.QMIPX, co.QMIP_{le}X, co.QMIP_{ne}X
∃X: cocap.beta_2PXCZKX, CohX, DQPX, Nearly-PX
Likeliest blank:
∀X: beta_2PX? USX, co.A_0PPX, co.RP^{PromiseUP}X
∀X: cocap.beta_2PX? APPX, AmpMPX, BQP/qpolyX, C_=PX, HeurBPPX, P-SelX, QSZKX, XOR-MIP*[2,1]X
Unlikeliest blank:
∀X: NLINSPACEX, QX, cocap.compIPX? cocap.beta_2PX
Blank case count: 52 ⊆? beta_2PX? 111

betaP: Limited-Nondeterminism NP [KF84]

betaP in the Zoo.

Best inclusions:
∀X: beta_2PXbetaPXNPX, QPX
Best separations:
∃X: cocap.betaPXQPLINX
Unlikeliest blank:
∀X: betaPX? BQP/logX, NLINX, NTX, UPX, polyLX
∀X: cocap.betaPX? AC^0/polyX, P/logX, YPX, cocap.NLINX, cocap.UPX
Blank case count: 52 ⊆? betaPX? 111

BH: Boolean Hierarchy Over NP [WW85]

BH in the Zoo.

Best inclusions:
∀X: BH_2XBHXP^{NP[log]}X
Best separations:
∃X: P^{NP[log]}XBHXBH_2X
Blank case count: 23 ⊆? BHX? 12

BH_2: Second Level of Boolean Hierarchy

Best inclusions:
∀X: USXBH_2XBHX
Best separations:
∃X: BHXBH_2X
Unlikeliest blank:
∀X: BH_2X? cocap.USX
Blank case count: 23 ⊆? BH_2X? 15

BP.PP: PP with BP operator

Best inclusions: [MW05]
∀X: PHX, PPX, QAMXBP.PPXCHX, PP/polyX
Unlikeliest blank:
∀X: Almost-PSPACEX, QRGX? BP.PPX
Blank case count: 76 ⊆? BP.PPX? 16

BPE: Bounded-Error Probabilistic E

BPE in the Zoo.

Best inclusions:
∀X: BPQPX, RPEXBPEXBPEXPX, cocap.MA_EX
Best separations:
∃X: cocap.UPXBPEXSEHX
Likeliest blank:
∀X: YPX, ZBQPX, cocap.compNPX? BPEX
Unlikeliest blank:
∀X: HeurBPPX? BPEX? AvgEX
Blank case count: 58 ⊆? BPEX? 3

BPEE: Bounded-Error Probabilistic EE

BPEE in the Zoo.

Best inclusions:
∀X: BPEXPX, EEXBPEEXEESPACEX
Best separations:
∃X: +EXPX, cocap.NEXPXBPEEXNEEXPX
Likeliest blank:
∀X: CheckX, QRGX, cocap.QMA(2)X, cocap.XOR-MIP*[2,1]X? BPEEX
Blank case count: 26 ⊆? BPEEX? 0

BPEXP: Bounded-Error Probabilistic EXP

Best inclusions:
∀X: Almost-PSPACEX, BPEX, EXPXBPEXPXBPEEX, cocap.MA_{EXP}X
Best separations:
∃X: cocap.UEXBPEXPXNEEX
Blank case count: 26 ⊆? BPEXPX? 2

BPL: Bounded-Error Probabilistic L

BPL in the Zoo.

Best inclusions: [Nis92]
∀X: RLXBPLXL/polyX, PLX, SCX
Likeliest blank:
∀X: BPLX? +SAC^1X, AC^1X, C_=LX
Unlikeliest blank:
∀X: NC^2X? BPLX
Blank case count: 45 ⊆? BPLX? 45

BPP: Bounded-Error Probabilistic Polynomial-Time

BPP in the Zoo.

Best inclusions:
∀X: RPXBPPXAVBPPX, BPP/logX, BPQPX, CheckX, FHX, TreeBQPX, cocap.N.BPPX, cocap.NISZKX, cocap.PZKX, cocap.WAPPX, cocap.XOR-MIP*[2,1]X
Best separations:
∃X: BPPXDelta_2PX, NEX
Likeliest blank:
∀X: BPPX? SF_4X
Unlikeliest blank:
∀X: AVBPPX, AmpP-BQPX, CheckX, FHX, NISZKX, PZKX, XOR-MIP*[2,1]X, cocap.NISZK_hX, cocap.WAPPX? BPPX
Blank case count: 29 ⊆? BPPX? 39

BPP//log: BPP With Logarithmic Randomness-Dependent Advice [TV02]

BPP//log in the Zoo.

Best inclusions:
∀X: BPP/rlogXBPP//logXP/polyX
Best separations:
∃X: SPARSEXBPP//logX
Likeliest blank:
∀X: IC[log,poly]X, TALLYX, YPX? BPP//logX? BQP/qlogX
Unlikeliest blank:
∀X: BPP//logX? BPP/logX, IC[log,poly]X, cocap.NP/oneX
Blank case count: 54 ⊆? BPP//logX? 27

BPP/log: BPP With Logarithmic Karp-Lipton Advice

BPP/log in the Zoo.

Best inclusions:
∀X: BPPX, P/logXBPP/logXBPP/mlogX, BQP/logX
Unlikeliest blank:
∀X: BPP//logX, CZKX, WAPPX, YPPX, cocap.frIPX? BPP/logX
Blank case count: 55 ⊆? BPP/logX? 21

BPP/mlog: BPP With Logarithmic Deterministic Merlin-Like Advice

BPP/mlog in the Zoo.

Best inclusions:
∀X: BPP/logXBPP/mlogXBPP/rlogX, BQP/mlogX
Likeliest blank:
∀X: BPP/mlogX? BQP/logX
Unlikeliest blank:
∀X: IC[log,poly]X, P-SelX? BPP/mlogX
Blank case count: 56 ⊆? BPP/mlogX? 23

BPP/rlog: BPP With Logarithmic Randomized Advice

BPP/rlog in the Zoo.

Best inclusions:
∀X: BPP/mlogXBPP/rlogXBPP//logX, BQP/qlogX
Likeliest blank:
∀X: BPP/rlogX? BQP/mlogX
Blank case count: 55 ⊆? BPP/rlogX? 25

BPP^{NP}: BPP With NP Oracle

Best inclusions: [HHT97]
∀X: AMX, BPP_{path}X, RP^{NP}XBPP^{NP}XDelta_3PX, SQGX
Likeliest blank:
∀X: cocap.N.NISZKX? BPP^{NP}X
Unlikeliest blank:
∀X: Delta_3PX, SQGX? BPP^{NP}X
Blank case count: 101 ⊆? BPP^{NP}X? 13

BPP_{path}: Threshold BPP [HHT97]

BPP_{path} in the Zoo.

Best inclusions: [HHT97] [HHT97] [HHT97] [BGM02]
∀X: P^{NP[log]}X, SBPXBPP_{path}XBPP^{NP}X, PPX
Likeliest blank:
∀X: FewX, TreeBQPX? BPP_{path}X
Unlikeliest blank:
∀X: APPX, A_0PPX, P^{NP[log^2]}X? BPP_{path}X
Blank case count: 80 ⊆? BPP_{path}X? 18

BPQP: Bounded-Error Probabilistic QP [CNS99]

BPQP in the Zoo.

Best inclusions:
∀X: BPPX, QPXBPQPXBPEX, QPSPACEX
Best separations: [BBF98] [Hel86]
∃X: BPQPX+EXPX, EXP^{NP}X
Likeliest blank:
∀X: NTX, cocap.CSLX, cocap.NLINX? BPQPX? NEXP/polyX, SEHX
Unlikeliest blank:
∀X: CZKX, DQPX, NT*X, QSZKX, WAPPX, YQPX, frIPX? BPQPX? BQP/mpolyX, SEHX
Blank case count: 68 ⊆? BPQPX? 9

BQP: Bounded-Error Quantum Polynomial-Time

BQP in the Zoo.

Best inclusions: [FR98] [Aar02b]
∀X: AmpP-BQPX, FHX, QCFLX, QNCX, RQPXBQPXAWPPX, BQP/logX, DQPX, YQPX, cocap.NIQSZKX, cocap.QCMAX
Best separations: [Aar02]
∃X: NISZK_hXBQPXMAX
Blank case count: 21 ⊆? BQPX? 79

BQP/log: BQP With Logarithmic-Size Karp-Lipton Advice

BQP/log in the Zoo.

Best inclusions:
∀X: BPP/logX, BQPXBQP/logXBQP/mlogX
Best separations:
∃X: IC[log,poly]X, P-SelX, QPLINXBQP/logX
Likeliest blank:
∀X: BPP/mlogX? BQP/logX
Unlikeliest blank:
∀X: BQP/mlogX, DQPX, QSZKX, YQPX, betaPX? BQP/logX
Blank case count: 53 ⊆? BQP/logX? 18

BQP/mlog: BQP With Logarithmic-Size Deterministic Merlin-Like Advice

BQP/mlog in the Zoo.

Best inclusions:
∀X: BPP/mlogX, BQP/logXBQP/mlogXBQP/qlogX
Best separations: [NY03]
∃X: BQP/qlogXBQP/mlogX
Likeliest blank:
∀X: BPP/rlogX? BQP/mlogX
Unlikeliest blank:
∀X: QPLINX? BQP/mlogX? BQP/logX, cocap.NP/oneX
Blank case count: 54 ⊆? BQP/mlogX? 19

BQP/mpoly: BQP With Polynomial-Size Deterministic Merlin-Like Advice

BQP/mpoly in the Zoo.

Best inclusions:
∀X: BQP/polyXBQP/mpolyXBQP/qpolyX
Likeliest blank:
∀X: YQPX? BQP/mpolyX? BQP/polyX
Unlikeliest blank:
∀X: BPQPX, NLINSPACEX, NT*X, SUBEXPX, frIPX? BQP/mpolyX
Blank case count: 61 ⊆? BQP/mpolyX? 13

BQP/poly: BQP With Polynomial-Size Karp-Lipton Advice

BQP/poly in the Zoo.

Best inclusions: [NY03]
∀X: BQP/qlogX, P/polyXBQP/polyXBQP/mpolyX
Best separations:
∃X: NTX, compNPX, polyLXBQP/polyX
Likeliest blank:
∀X: BQP/mpolyX? BQP/polyX
Unlikeliest blank:
∀X: BQP/qpolyX? BQP/polyX
Blank case count: 49 ⊆? BQP/polyX? 12

BQP/qlog: BQP With Logarithmic-Size Quantum Advice

BQP/qlog in the Zoo.

Best inclusions: [NY03]
∀X: BPP/rlogX, BQP/mlogXBQP/qlogXBQP/polyX
Best separations: [NY03]
∃X: SPARSEXBQP/qlogXBQP/mlogX, NP/logX
Likeliest blank:
∀X: BPP//logX, IC[log,poly]X, TALLYX, YPX? BQP/qlogX
Blank case count: 53 ⊆? BQP/qlogX? 12

BQP/qpoly: BQP With Polynomial-Size Quantum Advice

BQP/qpoly in the Zoo.

Best inclusions: [Aar04b]
∀X: BQP/mpolyX, YQPXBQP/qpolyXPP/polyX
Best separations: [BBB+97]
∃X: cocap.UPXBQP/qpolyX
Likeliest blank:
∀X: cocap.NISZKX, cocap.NLINX, cocap.PZKX, cocap.WAPPX, cocap.beta_2PX, cocap.compNPX? BQP/qpolyX
Unlikeliest blank:
∀X: BQP/qpolyX? (NP-cap-coNP)/polyX, BQP/polyX, Nearly-PX, cocap.MIP*X
Blank case count: 59 ⊆? BQP/qpolyX? 14

C_=L: Exact-Counting L

C_=L in the Zoo.

Best inclusions:
∀X: C_=LXPLX
∀X: NLX, SPLXcocap.C_=LX
Likeliest blank:
∀X: BPLX? C_=LX? co.C_=LX
∀X: cocap.C_=LX? +L/polyX, +SAC^1X, AC^1X
Blank case count: 65 ⊆? C_=LX? 96

C_=P: Exact-Counting Polynomial-Time

C_=P in the Zoo.

Best inclusions: [Vya03] [BHR00]
∀X: EPXC_=PXco.A_0PPX
∀X: WPPXcocap.C_=PX
Best separations:
∃X: NPXC_=PX
Likeliest blank:
∀X: QAC^0X, QCFLX, QNC^0X, co.EPX, cocap.NLINX, cocap.RNCX, cocap.beta_2PX, cocap.compNPX? C_=PX? A_0PPX
Unlikeliest blank:
∀X: USX, co.A_0PPX, co.N.NISZKX, co.QMA(2)X, co.RP^{PromiseUP}X, co.SBPX? C_=PX? Mod_3PX, Mod_5PX, NT*X, S_2PX, WPPX
∀X: APPX, AVBPPX, CZKX, DQPX, QSZKX, XOR-MIP*[2,1]X, cocap.A_0PPX, cocap.N.NISZKX, cocap.QMA(2)X, cocap.RP^{PromiseUP}X, cocap.SBPX, cocap.USX, frIPX? cocap.C_=PX
Blank case count: 205 ⊆? C_=PX? 78

CFL: Context-Free Languages

CFL in the Zoo.

Best inclusions: [Bra77]
∀X: CFLX1NAuxPDA^pX, GCSLX, NLINX, QCFLX
∀X: DCFLX, MAJORITYXcocap.CFLX
Best separations: [GG66] [MC00]
∃X: QCFLXCFLXDCFLX
Likeliest blank:
∀X: CFLX? co.1NAuxPDA^pX, co.CSLX, co.QX
∀X: cocap.CFLX? SCX
Unlikeliest blank:
∀X: 1NAuxPDA^pX, CSLX? cocap.CFLX
Blank case count: 37 ⊆? CFLX? 105

CH: Counting Hierarchy [Wag86]

CH in the Zoo.

Best inclusions: [Ogi94] [Her97]
∀X: BP.PPX, MP^{#P}X, SF_4XCHXPSPACEX
Likeliest blank:
∀X: RG[1]X, cocap.AM[polylog]X, cocap.CSLX, cocap.CZKX, cocap.NIQSZKX, cocap.compIPX, polyLX? CHX
Blank case count: 59 ⊆? CHX? 15

Check: Checkable Languages [BK89]

Check in the Zoo.

Best inclusions:
∀X: BPPXCheckXcocap.frIPX
Likeliest blank:
∀X: cocap.compNPX? CheckX? +EXPX, BPEEX, EXP/polyX, NE/polyX, QMA(2)X, QMIPX, QMIP_{le}X, QRGX
Unlikeliest blank:
∀X: CZKX, NT*X, QX, WAPPX, YPPX, frIPX? CheckX? BPPX, QAC^0X, QNC_f^0X, ZQPX
Blank case count: 55 ⊆? CheckX? 184

Coh: Coherent Languages [Yao90b]

Coh in the Zoo.

Best inclusions: [Yao90b]
∀X: frIPXCohXALLX
Best separations:
∃X: EQPX, cocap.UPX, cocap.beta_2PX, polyLXCohXAHX, NEXP/polyX, Nearly-PX
Likeliest blank:
∀X: AVBPPX, AvgPX, FHX, NTX, P-SelX, P/logX, QAC^0X, QCFLX, QNC^0X, TALLYX, TreeBQPX, YPX, ZBQPX, cocap.CSLX, cocap.NISZKX, cocap.NLINX, cocap.PZKX, cocap.WAPPX, cocap.XOR-MIP*[2,1]X? CohX
Unlikeliest blank:
∀X: HeurBPPX, Nearly-PX, P-SelX, P/polyX, PL_{infty}X? CohX? P-SelX, cocap.MIP*X
Blank case count: 70 ⊆? CohX? 7

compIP: Competitive IP Proof System

compIP in the Zoo.

Best inclusions: [BG94]
∀X: compNPXcompIPXIPX, frIPX
Likeliest blank:
∀X: cocap.HalfPX, cocap.RNCX? compIPX
∀X: cocap.compIPX? AM[polylog]X, CHX, EHX, NE/polyX, PP/polyX, QIP[2]X, QMA(2)X, QS_2PX, RG[1]X
Unlikeliest blank:
∀X: compIPX? AvgPX, LWPPX, NLINX, cocap.USX, compNPX
∀X: AVBPPX, AmpP-BQPX, CZKX, FHX, NT*X, RBQPX, WAPPX, XOR-MIP*[2,1]X, frIPX? cocap.compIPX? NTX, P/logX, YPX, cocap.NLINX, cocap.UPX, cocap.beta_2PX, cocap.compNPX, polyLX
Blank case count: 126 ⊆? compIPX? 332

compNP: Competitive NP Proof System

compNP in the Zoo.

Best inclusions:
∀X: compNPXNPX, compIPX
∀X: PXcocap.compNPX
Best separations:
∃X: compNPX+PX, BQP/polyX, Mod_3PX, Mod_5PX, SUBEXPX, co.NP/polyX
∃X: cocap.compNPXDQPX
Likeliest blank:
∀X: compNPX? USX, co.A_0PPX, co.MA_EX, co.QMIPX, co.QMIP_{le}X, co.QMIP_{ne}X, co.RP^{PromiseUP}X
∀X: cocap.compNPX? APPX, AmpMPX, AvgEX, BPEX, BQP/qpolyX, CZKX, C_=PX, CheckX, HeurBPPX, Nearly-PX, P-SelX, QSZKX, UEX, XOR-MIP*[2,1]X
Unlikeliest blank:
∀X: RBQPX, compIPX? compNPX
∀X: QX, YPPX, ZBQPX, cocap.compIPX? cocap.compNPX
Blank case count: 57 ⊆? compNPX? 177

CSL: Context Sensitive Languages

CSL in the Zoo.

Best inclusions: [Kur64]
∀X: GCSLXCSLXNLINSPACEX
∀X: PBPXcocap.CSLX
Best separations:
∃X: +SAC^0X, LINX, SAC^0XCSLX
∃X: cocap.CSLXDCFLX, LX
Likeliest blank:
∀X: NC^0X, co.CFLX, cocap.1NAuxPDA^pX? CSLX
∀X: cocap.CSLX? BPQPX, CHX, CohX, DQPX, HeurBPPX, Nearly-PX, P-SelX, PP/polyX, QMIPX, QMIP_{le}X, QMIP_{ne}X, SQGX, SUBEXPX
Unlikeliest blank:
∀X: CSLX? AC^0/polyX, LINX, QAC^0X, QNC_f^0X, cocap.CFLX, cocap.R_HLX, cocap.ULX
Blank case count: 24 ⊆? CSLX? 576

CZK: Computational Zero-Knowledge

CZK in the Zoo.

Best inclusions:
∀X: CZKXIPX
∀X: SZKXcocap.CZKX
Best separations: [Imp..] [Imp..]
∃X: UPX, cocap.beta_2PXCZKX
Likeliest blank:
∀X: YPX, ZBQPX, cocap.NLINX, cocap.UPX, cocap.WAPPX, cocap.compNPX? CZKX? co.QMIPX, co.QMIP_{le}X, co.QMIP_{ne}X
∀X: cocap.CZKX? AM[polylog]X, CHX, DQPX, EHX, NE/polyX, PP/polyX, QIP[2]X
Unlikeliest blank:
∀X: CZKX? AC^0/polyX, AVBPPX, AvgEX, BPP/logX, BPQPX, CheckX, IC[log,poly]X, P-CloseX, YPPX, cocap.C_=PX, cocap.N.BPPX, cocap.NISZKX, cocap.NP/oneX, cocap.PZKX, cocap.WAPPX, cocap.XOR-MIP*[2,1]X, cocap.compIPX
∀X: NLINSPACEX, NT*X, QX, WAPPX, YQPX, cocap.EPX, frIPX? cocap.CZKX
Blank case count: 116 ⊆? CZKX? 304

DCFL: Deterministic CFL [GG66]

DCFL in the Zoo.

Best inclusions: [Coo79]
∀X: REGXDCFLXLINX, SCX, cocap.CFLX
Best separations: [GG66] [GG66]
∃X: CFLX, cocap.CSLXDCFLXREGX
Likeliest blank:
∀X: DCFLX? +L/polyX, ALX, QNC^1X
Unlikeliest blank:
∀X: PBPX, cocap.1NAuxPDA^pX, cocap.GCSLX? DCFLX
Blank case count: 12 ⊆? DCFLX? 46

Delta_2P: P With NP Oracle

Delta_2P in the Zoo.

Best inclusions: [Ogi94] [RS98]
∀X: P^{FewP}X, P^{NP[log^2]}XDelta_2PXP^{QMA}X, SF_2X, S_2PX
Best separations: [Bei94] [CS92]
∃X: BPPX, EQPXDelta_2PXPPX, P^{NP[log^2]}X
Blank case count: 21 ⊆? Delta_2PX? 7

Delta_3P: P With Sigma_2P Oracle

Best inclusions:
∀X: BPP^{NP}X, Sigma_2PXDelta_3PXcocap.Sigma_3PX
Best separations: [Yao85]
∃X: cocap.Sigma_3PXDelta_3PX
Likeliest blank:
∀X: Delta_3PX? SQGX
Likeliest open: [Aar03b]
∀X: TreeBQPX? Delta_3PX
Unlikeliest blank:
∀X: Delta_3PX? BPP^{NP}X
Unlikeliest open: [Aar03b]
∀X: TreeBQPX? Delta_3PX
Blank case count: 94 ⊆? Delta_3PX? 15

DQP: Dynamical Quantum Polynomial-Time [Aar02b]

DQP in the Zoo.

Best inclusions: [Aar02b] [Aar02b] [Aar02b]
∀X: BQPX, SZKXDQPXEXPX
Best separations:
∃X: AvgPX, NTX, YPX, cocap.NLINX, cocap.UPX, cocap.beta_2PX, cocap.compNPXDQPX
Likeliest blank:
∀X: AVBPPX, cocap.CSLX, cocap.CZKX, cocap.NIQSZKX, cocap.WAPPX, polyLX? DQPX
Likeliest open:
∀X: DQPX? Almost-PSPACEX, ESPACEX, PP/polyX, QMIPX, QMIP_{le}X, QMIP_{ne}X, QRGX
Unlikeliest blank:
∀X: DQPX? (NP-cap-coNP)/polyX, AVBPPX, AvgEX, BPQPX, BQP/logX, ModPX, Nearly-PX, P-SelX, SF_2X, S_2PX, YQPX, cocap.C_=PX, cocap.NISZKX, cocap.NP/oneX, cocap.QCMAX, cocap.RP^{PromiseUP}X, cocap.WAPPX, cocap.XOR-MIP*[2,1]X
Unlikeliest open:
∀X: DQPX? Almost-PSPACEX, ESPACEX, PP/polyX, QMIPX, QMIP_{le}X, QMIP_{ne}X, QRGX
Blank case count: 19 ⊆? DQPX? 77

E: Exponential Time With Linear Exponent

E in the Zoo.

Best inclusions: [GHJ+91]
∀X: AvgPX, NLINSPACEX, NTX, QX, SUBEXPXEXAvgEX, EXPX, ZPEX, cocap.UEX
Best separations:
∃X: ZPPXEX
Unlikeliest blank:
∀X: EX? HeurBPPX
Blank case count: 21 ⊆? EX? 1

EE: Double-Exponential Time With Linear Exponent

EE in the Zoo.

Best inclusions:
∀X: AvgEX, ESPACEX, EXPXEEXBPEEX, EEXPX, cocap.NEEX
Blank case count: 27 ⊆? EEX? 0

EEE: Triple-Exponential Time With Linear Exponent

EEE in the Zoo.

Best inclusions:
∀X: EESPACEX, EEXPXEEEXcocap.NEEEX
Best separations:
∃X: cocap.NEEXPXEEEX
Likeliest blank:
∀X: cocap.MIP_{EXP}X? EEEX
Blank case count: 9 ⊆? EEEX? 0

EESPACE: Double-Exponential Space With Linear Exponent

EESPACE in the Zoo.

Best inclusions:
∀X: BPEEX, EXPSPACEX, NEEXEESPACEXEEEX
Best separations:
∃X: EEXPXEESPACEX
Blank case count: 9 ⊆? EESPACEX? 0

EEXP: Double-Exponential Time

EEXP in the Zoo.

Best inclusions:
∀X: EEX, EXPSPACEXEEXPXEEEX, cocap.NEEXPX
Best separations:
∃X: cocap.NEEXEEXPXEESPACEX
Blank case count: 9 ⊆? EEXPX? 0

EH: Exponential-Time Hierarchy With Linear Exponent

EH in the Zoo.

Best inclusions:
∀X: MA_EX, PHXEHXESPACEX, EXPHX
Best separations:
∃X: EHXNEXP/polyX
Likeliest blank:
∀X: EQPX, FHX, NT*X, QAC^0X, QCFLX, QNC^0X, RG[1]X, UAPX, cocap.AM[polylog]X, cocap.CZKX, cocap.compIPX? EHX? NEXP^{NP}X, PEXPX
Unlikeliest blank:
∀X: Almost-PSPACEX, QPSPACEX, QRGX? EHX
Blank case count: 109 ⊆? EHX? 4

ELEMENTARY: Iterated Exponential Time

ELEMENTARY in the Zoo.

Best inclusions:
∀X: NEEEXELEMENTARYXPRX
Best separations: [HS65]
∃X: PRXELEMENTARYX
Blank case count: 6 ⊆? ELEMENTARYX? 0

EP: NP with 2^k accepting paths [BHR00]

EP in the Zoo.

Best inclusions: [BHR00] [BHR00]
∀X: FewPX, HalfPXEPXC_=PX, Mod_3PX, Mod_5PX, NPX, cocap.A_0PPX
Likeliest blank:
∀X: EPX? co.C_=PX
∀X: cocap.EPX? APPX
Unlikeliest blank:
∀X: EPX? FewPX, UAPX
∀X: cocap.EPX? Nearly-PX, cocap.CZKX, cocap.UPX
Blank case count: 55 ⊆? EPX? 55

EQP: Exact Quantum Polynomial-Time

EQP in the Zoo.

Best inclusions: [FR98] [BB92]
∀X: HalfPXEQPXLWPPX, ZQPX
Best separations: [BV97]
∃X: EQPXCohX, Delta_2PX, P/polyX
Likeliest blank:
∀X: EQPX? EHX, FHX, HeurBPPX, MIPX, MIP*X, MPX, NE/polyX, RG[1]X, SF_4X
Unlikeliest blank:
∀X: EQPX? AvgPX, NTX, QPLINX, polyLX
Blank case count: 13 ⊆? EQPX? 123

ESPACE: Exponential Space With Linear Exponent

ESPACE in the Zoo.

Best inclusions:
∀X: EHX, QPSPACEXESPACEXEEX, EXPSPACEX
Best separations:
∃X: EXPXESPACEXEXPHX
Likeliest blank:
∀X: AVBPPX, QS_2PX, RGX, cocap.QIP[2]X? ESPACEX
Likeliest open:
∀X: DQPX? ESPACEX
Unlikeliest blank:
∀X: ESPACEX? PEXPX
Unlikeliest open:
∀X: DQPX? ESPACEX
Blank case count: 38 ⊆? ESPACEX? 1

EXP: Exponential Time

EXP in the Zoo.

Best inclusions: [Aar02b] [KM92] [Gut05]
∀X: DQPX, EX, HeurBPPX, RGX, SQGXEXPX+EXPX, BPEXPX, EEX, EXP/polyX, cocap.NEXPX
Best separations:
∃X: EXPXESPACEX
Blank case count: 27 ⊆? EXPX? 1

EXP/poly: Exponential Time With Polynomial-Size Advice

EXP/poly in the Zoo.

Best inclusions:
∀X: EXPX, PP/polyXEXP/polyXNEXP/polyX
Best separations:
∃X: ZPEX, cocap.UEXEXP/polyX
Likeliest blank:
∀X: CheckX, QRGX, cocap.QMA(2)X, cocap.XOR-MIP*[2,1]X? EXP/polyX
Blank case count: 30 ⊆? EXP/polyX? 1

EXP^{NP}: EXP with NP oracle

Best inclusions:
∀X: NEXPXEXP^{NP}Xcocap.NEXP^{NP}X
Best separations: [Hel86]
∃X: BPQPXEXP^{NP}XNEXP/polyX
Likeliest blank:
∀X: Almost-PSPACEX? EXP^{NP}X? PEXPX, SEHX
Unlikeliest blank:
∀X: +EXPX? EXP^{NP}X? PEXPX, SEHX
Blank case count: 8 ⊆? EXP^{NP}X? 2

EXPH: Exponential-Time Hierarchy

Best inclusions:
∀X: EHX, NEXP^{NP}XEXPHXEXPSPACEX
Best separations: [Hem89]
∃X: ESPACEX, SEHXEXPHX
Likeliest blank:
∀X: +EXPX, PEXPX, QPSPACEX, cocap.IP_{EXP}X? EXPHX
Unlikeliest blank:
∀X: EXPHX? cocap.NEXP^{NP}X
Blank case count: 15 ⊆? EXPHX? 3

EXPSPACE: Exponential Space

EXPSPACE in the Zoo.

Best inclusions:
∀X: +EXPX, ESPACEX, EXPHX, IP_{EXP}X, PEXPX, SEHXEXPSPACEXEESPACEX, EEXPX
Best separations:
∃X: AvgEXEXPSPACEX
Blank case count: 9 ⊆? EXPSPACEX? 0

Few: FewP With Flexible Acceptance Mechanism

Few in the Zoo.

Best inclusions: [Kob89]
∀X: FewPXFewXP^{FewP}X
Likeliest blank:
∀X: P^{FewP}X? FewX? BPP_{path}X, NE/polyX, P^{NP[log^2]}X
Unlikeliest blank:
∀X: SPPX? FewX
Blank case count: 38 ⊆? FewX? 15

FewL: Logspace Analogue of FewP [BDH+92]

Best inclusions:
∀X: FewULXFewLXLFewX
Likeliest blank:
∀X: co.ULX? FewLX
∀X: cocap.FewLX? LogFewX
Unlikeliest blank:
∀X: FewLX? co.FewULX
∀X: LogFewX? cocap.FewLX
Blank case count: 87 ⊆? FewLX? 66

FewP: NP With Few Witnesses

FewP in the Zoo.

Best inclusions: [BHR00]
∀X: UPXFewPXEPX, FewX
Best separations: [Rub88]
∃X: FewPXUPX
Likeliest blank:
∀X: FewPX? USX, co.RP^{PromiseUP}X
∀X: cocap.FewPX? UAPX, UEX
Unlikeliest blank:
∀X: EPX? FewPX
Blank case count: 61 ⊆? FewPX? 33

FewUL: Alternate Name for LogFewNL [BJL+91]

Best inclusions:
∀X: ULXFewULXFewLX, LogFewX
Likeliest blank:
∀X: cocap.FewULX? ULX
Unlikeliest blank:
∀X: co.FewLX? FewULX
∀X: ULX? cocap.FewULX
Blank case count: 85 ⊆? FewULX? 62

FH: Fourier Hierarchy [Shi03]

FH in the Zoo.

Best inclusions:
∀X: BPPXFHXBQPX
Likeliest blank:
∀X: EQPX, QAC^0X, QCFLX, QNC^0X, TreeBQPX, ZBQPX? FHX? CohX, EHX, HeurBPPX, MIPX, MIP*X, MPX, NE/polyX, RG[1]X
Unlikeliest blank:
∀X: NIQSZKX, WAPPX? FHX? AC^0/polyX, BPPX, IC[log,poly]X, P-CloseX, YPPX, cocap.compIPX
Blank case count: 38 ⊆? FHX? 127

FOLL: First-Order loglog n [BKL+00]

FOLL in the Zoo.

Best inclusions:
∀X: AC^0XFOLLXAC^1X
Best separations: [BKL+00] [BKL+00] [Smo87]
∃X: PARITYXFOLLXAC^0X
Likeliest blank:
∀X: MAJORITYX? FOLLX? +L/polyX, +SAC^1X, AC^0/polyX, ALX, MAC^0X, QNC^1X, SCX
Unlikeliest blank:
∀X: MAC^0X? FOLLX? LINX, MAC^0X
Blank case count: 4 ⊆? FOLLX? 27

frIP: Function-Restricted IP Proof Systems

frIP in the Zoo.

Best inclusions: [Yao90b] [FRS88] [BG94]
∀X: compIPXfrIPXCohX, MIPX
∀X: CheckXcocap.frIPX
Likeliest blank:
∀X: frIPX? co.MIP_{EXP}X, co.NEEX
Unlikeliest blank:
∀X: frIPX? AVBPPX, AvgEX, BPQPX, BQP/mpolyX, CheckX, N.BPPX, Nearly-PX, WAPPX, YQPX, cocap.AM[polylog]X, cocap.CZKX, cocap.C_=PX, cocap.NIQSZKX, cocap.QCMAX, cocap.XOR-MIP*[2,1]X, cocap.compIPX
∀X: cocap.frIPX? AC^0/polyX, BPP/logX, IC[log,poly]X, P-CloseX, YPPX, cocap.N.BPPX, cocap.WAPPX
Blank case count: 101 ⊆? frIPX? 304

GCSL: Growing CSL [DW86]

GCSL in the Zoo.

Best inclusions: [DW86] [DW86]
∀X: CFLXGCSLXCSLX, QX, SAC^1X
Likeliest blank:
∀X: cocap.GCSLX? 1NAuxPDA^pX, NLINX, QCFLX
Unlikeliest blank:
∀X: co.SAC^0X? GCSLX? 3-PBPX
∀X: QCFLX? cocap.GCSLX? DCFLX
Blank case count: 37 ⊆? GCSLX? 119

HalfP: RP With Exactly Half Acceptance [BB92]

HalfP in the Zoo.

Best inclusions: [BB92]
∀X: HalfPXEPX, EQPX, RPX
∀X: PXcocap.HalfPX
Likeliest blank:
∀X: HalfPX? USX, YPPX, co.NEX, co.NP/logX, co.RP^{PromiseUP}X
∀X: cocap.HalfPX? +PX, AvgEX, IC[log,poly]X, Nearly-PX, P-SelX, UEX, compIPX
Unlikeliest blank:
∀X: HalfPX? ALX, NCX, SCX, cocap.NLINX
Blank case count: 29 ⊆? HalfPX? 152

HeurBPP: Heuristic BPP

HeurBPP in the Zoo.

Best inclusions:
∀X: AVBPPX, AvgPXHeurBPPXEXPX
Best separations:
∃X: cocap.UPXHeurBPPX
Likeliest blank:
∀X: EQPX, FHX, NTX, QAC^0X, QCFLX, QNC^0X, TreeBQPX, YPX, ZBQPX, cocap.CSLX, cocap.NISZKX, cocap.NLINX, cocap.PZKX, cocap.WAPPX, cocap.beta_2PX, cocap.compNPX, polyLX? HeurBPPX
Unlikeliest blank:
∀X: EX? HeurBPPX? AvgEX, BPEX, CohX, Nearly-PX
Blank case count: 78 ⊆? HeurBPPX? 10

IC[log,poly]: Logarithmic Instance Complexity, Polynomial Time [OKS+94]

IC[log,poly] in the Zoo.

Best inclusions:
∀X: P/logXIC[log,poly]XP/polyX
Best separations:
∃X: L/polyXIC[log,poly]XBQP/logX, NP/logX
Likeliest blank:
∀X: TALLYX, cocap.HalfPX, cocap.RNCX? IC[log,poly]X? BPP//logX, BQP/qlogX
Unlikeliest blank:
∀X: AVBPPX, AmpP-BQPX, BPP//logX, CZKX, FHX, P-CloseX, P-SelX, RBQPX, TC^0/polyX, WAPPX, XOR-MIP*[2,1]X, YPPX, cocap.frIPX? IC[log,poly]X? BPP/mlogX
Blank case count: 74 ⊆? IC[log,poly]X? 19

IP: Interactive Proof

IP in the Zoo.

Best inclusions:
∀X: AM[polylog]X, CZKX, compIPXIPXMIPX, MIP*X, PSPACEX, QIPX
Best separations: [AGH90]
∃X: IPXAM[polylog]X
Unlikeliest blank:
∀X: QMIPX, QMIP_{le}X, QMIP_{ne}X? IPX
Blank case count: 127 ⊆? IPX? 109

IP_{EXP}: Exponential Time Interactive Proof

Best inclusions:
∀X: AM_{EXP}XIP_{EXP}XEXPSPACEX, MIP_{EXP}X
Likeliest blank:
∀X: cocap.IP_{EXP}X? EXPHX
Blank case count: 33 ⊆? IP_{EXP}X? 16

L: Logarithmic Space

L in the Zoo.

Best inclusions: [Bor77]
∀X: NC^1X, PBPXLXcocap.R_HLX, cocap.ULX
Best separations:
∃X: cocap.CSLXLXLINX
Unlikeliest blank:
∀X: AC^1X? LX
Blank case count: 48 ⊆? LX? 18

L/poly: Nonuniform Logarithmic Space

L/poly in the Zoo.

Best inclusions:
∀X: BPLX, TC^0/polyXL/polyXNL/polyX
Best separations:
∃X: L/polyXIC[log,poly]X
Likeliest blank:
∀X: cocap.ULX? L/polyX
Blank case count: 109 ⊆? L/polyX? 11

L^{DET}: L-reduction to DET [Coo85]

Best inclusions: [CKS81] [BCP83] [BCP83]
∀X: PLXL^{DET}XALX, NC^2X
Likeliest blank:
∀X: +LX? L^{DET}X? PLX
Blank case count: 28 ⊆? L^{DET}X? 51

LFew: Logspace Analogue of Few [ARZ99]

Best inclusions: [ARZ99] [ARZ99]
∀X: FewLX, LogFewXLFewXNLX, SPLX
Blank case count: 39 ⊆? LFewX? 28

LIN: Linear Time

LIN in the Zoo.

Best inclusions:
∀X: DCFLXLINXPX, cocap.NLINX
Best separations:
∃X: LXLINXCSLX, QCFLX
Likeliest blank:
∀X: MAJORITYX? LINX? QNCX, polyLX
Unlikeliest blank:
∀X: 1NAuxPDA^pX, CSLX, FOLLX, QCFLX, QNC^1X? LINX? +SAC^0X, cocap.1NAuxPDA^pX
Blank case count: 36 ⊆? LINX? 56

LogFew: Logspace-Bounded Few [BDH+92]

LogFew in the Zoo.

Best inclusions:
∀X: FewULXLogFewXLFewX
Likeliest blank:
∀X: cocap.FewLX? LogFewX
Unlikeliest blank:
∀X: LogFewX? cocap.FewLX
Blank case count: 42 ⊆? LogFewX? 31

LWPP: Length-Dependent Wide PP [FFK94]

LWPP in the Zoo.

Best inclusions: [FR98]
∀X: EQPX, SPPXLWPPXWPPX
Best separations: [STT05]
∃X: WPPXLWPPX
Unlikeliest blank:
∀X: Mod_3PX, Mod_5PX, compIPX? LWPPX? UAPX
Blank case count: 38 ⊆? LWPPX? 36

MA: Merlin-Arthur

MA in the Zoo.

Best inclusions: [BGM02] [RS98]
∀X: N.BPPXMAXMA_EX, QCMAX, SBPX, S_2PX
∀X: YPPXcocap.MAX
Best separations: [FFK+93]
∃X: BQPXMAXN.BPPX
Blank case count: 96 ⊆? MAX? 56

MA_E: Exponential-Time MA With Linear Exponent

MA_E in the Zoo.

Best inclusions:
∀X: MAX, NEXMA_EXEHX, MA_{EXP}X
∀X: BPEXcocap.MA_EX
Best separations:
∃X: co.UPXMA_EX
Likeliest blank:
∀X: TreeBQPX, co.RBQPX, co.compNPX, cocap.NISZKX, cocap.PZKX, cocap.WAPPX? MA_EX
Unlikeliest blank:
∀X: QMIPX, QMIP_{le}X, QMIP_{ne}X? MA_EX
∀X: cocap.QMIPX, cocap.QMIP_{le}X, cocap.QMIP_{ne}X? cocap.MA_EX
Blank case count: 154 ⊆? MA_EX? 4

MA_{EXP}: Exponential-Time MA

MA_{EXP} in the Zoo.

Best inclusions: [Ver92]
∀X: MA_EX, NEXPXMA_{EXP}XAM_{EXP}X, PEXPX, cocap.NEXP^{NP}X
∀X: BPEXPXcocap.MA_{EXP}X
Blank case count: 30 ⊆? MA_{EXP}X? 4

MAC^0: Majority of AC^0

MAC^0 in the Zoo.

Best inclusions:
∀X: AC^0X, MAJORITYXMAC^0XTC^0X
Best separations:
∃X: PARITYXMAC^0X
Likeliest blank:
∀X: FOLLX? MAC^0X
Unlikeliest blank:
∀X: FOLLX? MAC^0X? FOLLX
Blank case count: 3 ⊆? MAC^0X? 16

MAJORITY: Majority or Minority of Input Bits

Best inclusions:
∀X: NONEXMAJORITYX(k>=5)-PBPX, MAC^0X, PT_1X, cocap.CFLX
Best separations: [Raz87]
∃X: MAJORITYXAC^0[2]X, PL_1X, QNC^0X, REGX
Likeliest blank:
∀X: MAJORITYX? AC^0/polyX, FOLLX, LINX, QACC^0X
Unlikeliest blank:
∀X: QNC^0X, cocap.SAC^0X? MAJORITYX
Blank case count: 3 ⊆? MAJORITYX? 10

MIP: Multi-Prover Interactive Proof

MIP in the Zoo.

Best inclusions: [FRS88]
∀X: IPX, frIPXMIPXQMIP_{ne}X
Likeliest blank:
∀X: EQPX, FHX, QAC^0X, QCFLX, QNC^0X, TreeBQPX, co.RBQPX? MIPX
Blank case count: 119 ⊆? MIPX? 167

MIP*: MIP With Quantum-Entangled Provers [CHT+04]

Best inclusions:
∀X: IPX, XOR-MIP*[2,1]XMIP*XQMIPX
Likeliest blank:
∀X: EQPX, FHX, QAC^0X, QCFLX, QNC^0X, TreeBQPX, co.RBQPX? MIP*X
∀X: cocap.MIP*X? AHX, NEXP/polyX
Unlikeliest blank:
∀X: NP/polyX? MIP*X
∀X: BQP/qpolyX, CohX, P-SelX, PL_{infty}X, cocap.NP/polyX? cocap.MIP*X
Blank case count: 188 ⊆? MIP*X? 239

MIP_{EXP}: Exponential-Time Multi-Prover Interactive Proof

MIP_{EXP} in the Zoo.

Best inclusions:
∀X: IP_{EXP}XMIP_{EXP}XNEEXPX
Best separations:
∃X: AvgEX, QPSPACEX, co.UEXMIP_{EXP}X
Likeliest blank:
∀X: co.QMA(2)X, co.XOR-MIP*[2,1]X, co.frIPX? MIP_{EXP}X? co.NEEEX
∀X: cocap.MIP_{EXP}X? EEEX
Unlikeliest blank:
∀X: MIP_{EXP}X? AM_{EXP}X, NE/polyX, cocap.NEXP^{NP}X
∀X: cocap.MIP_{EXP}X? cocap.AM_{EXP}X
Blank case count: 30 ⊆? MIP_{EXP}X? 32

Mod_3P: Mod-3 Polynomial-Time

Best inclusions:
∀X: EPX, SPPXMod_3PXModPX, SF_3X
Best separations: [BBF98]
∃X: Mod_5PX, NTX, ZPPX, compNPXMod_3PX+PX, Mod_5PX, PHX
Likeliest blank:
∀X: Mod_3PX? PP/polyX, SF_2X
Unlikeliest blank:
∀X: C_=PX? Mod_3PX? LWPPX
Blank case count: 35 ⊆? Mod_3PX? 21

Mod_5P: Mod-5 Polynomial-Time

Best inclusions:
∀X: EPX, SPPXMod_5PXModPX
Best separations: [BBF98]
∃X: Mod_3PX, NTX, ZPPX, compNPXMod_5PX+PX, Mod_3PX, PHX
Likeliest blank:
∀X: Mod_5PX? PP/polyX, SF_4X
Unlikeliest blank:
∀X: C_=PX? Mod_5PX? LWPPX
Blank case count: 35 ⊆? Mod_5PX? 23

ModP: Mod_kP With Arbitrary k [KT96]

ModP in the Zoo.

Best inclusions: [KT96]
∀X: +PX, Mod_3PX, Mod_5PXModPXAmpMPX
Likeliest blank:
∀X: AmpMPX? ModPX
Unlikeliest blank:
∀X: AVBPPX, Almost-PSPACEX, DQPX, QMIPX, QMIP_{le}X, QMIP_{ne}X, QRGX? ModPX
Blank case count: 191 ⊆? ModPX? 12

MP: Middle-Bit P [GKR+95]

MP in the Zoo.

Best inclusions: [Tod89]
∀X: AmpMPX, PHXMPXP^{#P[1]}X
Likeliest blank:
∀X: EQPX, FHX, QAC^0X, QCFLX, QNC^0X? MPX
Blank case count: 103 ⊆? MPX? 14

MP^{#P}: MP With #P Oracle

Best inclusions:
∀X: P^{PP}XMP^{#P}XCHX
Likeliest blank:
∀X: SF_2X, cocap.QAMX? MP^{#P}X
Likeliest open:
∀X: MP^{#P}X? P^{PP}X
Unlikeliest open:
∀X: MP^{#P}X? P^{PP}X
Blank case count: 66 ⊆? MP^{#P}X? 15

N.BPP: BPP With Existential Operator

N.BPP in the Zoo.

Best inclusions:
∀X: NPXN.BPPXMAX, N.NISZKX
∀X: BPPXcocap.N.BPPX
Best separations: [FFK+93]
∃X: MAXN.BPPX
Likeliest blank:
∀X: cocap.N.BPPX? (NP-cap-coNP)/polyX
Unlikeliest blank:
∀X: N.NISZKX, frIPX? N.BPPX
∀X: CZKX, RQPX, cocap.N.NISZKX, cocap.SBPX, cocap.frIPX? cocap.N.BPPX
Blank case count: 100 ⊆? N.BPPX? 49

N.NISZK: NISZK With Existential Operator

N.NISZK in the Zoo.

Best inclusions:
∀X: N.BPPX, NISZKXN.NISZKXNP/polyX, Sigma_2PX
Likeliest blank:
∀X: YPPX, co.NISZKX, cocap.NISZK_hX, cocap.PZKX, cocap.WAPPX? N.NISZKX? co.Sigma_2PX
∀X: cocap.N.NISZKX? BPP^{NP}X, QMIPX, QMIP_{le}X, QMIP_{ne}X
Unlikeliest blank:
∀X: QMA(2)X, co.WAPPX? N.NISZKX? N.BPPX, NP/oneX, WAPPX, XOR-MIP*[2,1]X, co.C_=PX
∀X: cocap.QMIPX, cocap.QMIP_{le}X, cocap.QMIP_{ne}X? cocap.N.NISZKX? (NP-cap-coNP)/polyX, cocap.C_=PX, cocap.N.BPPX, cocap.NIQSZKX, cocap.NP/oneX, cocap.WAPPX, cocap.XOR-MIP*[2,1]X
Blank case count: 141 ⊆? N.NISZKX? 147

NC: Nick's Class

NC in the Zoo.

Best inclusions: [Bor77]
∀X: NC^2XNCXPX, cocap.RNCX, polyLX
Best separations:
∃X: NCXNC^2X
Unlikeliest blank:
∀X: HalfPX, QNCX? NCX
Blank case count: 20 ⊆? NCX? 17

NC^0: Level 0 of NC

NC^0 in the Zoo.

Best inclusions:
∀X: NONEXNC^0X+SAC^0X, PL_1X, QNC^0X, cocap.SAC^0X
Best separations:
∃X: NC^0X2-PBPX, SPARSEX
Likeliest blank:
∀X: NC^0X? 1NAuxPDA^pX, CSLX, QX, QCFLX
Unlikeliest blank:
∀X: QNC^0X, cocap.SAC^0X? NC^0X
Blank case count: 2 ⊆? NC^0X? 27

NC^1: Level 1 of NC

NC^1 in the Zoo.

Best inclusions: [Bor77] [Bar89]
∀X: (k>=5)-PBPX, REGX, TC^0XNC^1XLX, QNC^1X
Best separations: [Mil92]
∃X: AC^1XNC^1X
Blank case count: 49 ⊆? NC^1X? 16

NC^2: Level 2 of NC

NC^2 in the Zoo.

Best inclusions: [BCP83]
∀X: +SAC^1X, AC^1X, L^{DET}XNC^2XNCX
Best separations:
∃X: NCXNC^2XAC^1X
Unlikeliest blank:
∀X: NC^2X? BPLX, SPLX
Blank case count: 12 ⊆? NC^2X? 26

NE: Nondeterministic E

NE in the Zoo.

Best inclusions:
∀X: NPX, RPEX, UEXNEXMA_EX, NE/polyX, NEXPX
Best separations:
∃X: BPPXNEX
Likeliest blank:
∀X: YPPX, co.HalfPX, co.RNCX? NEX
Blank case count: 47 ⊆? NEX? 0

NE/poly: Nonuniform NE

NE/poly in the Zoo.

Best inclusions:
∀X: NEX, NP/polyXNE/polyXNEXP/polyX
Likeliest blank:
∀X: AVBPPX, CheckX, EQPX, FHX, FewX, NT*X, QAC^0X, QCFLX, QNC^0X, TreeBQPX, UAPX, cocap.AM[polylog]X, cocap.CZKX, cocap.RP^{PromiseUP}X, cocap.USX, cocap.XOR-MIP*[2,1]X, cocap.compIPX? NE/polyX
Unlikeliest blank:
∀X: MIP_{EXP}X, NEXP/polyX, PEXPX, QPSPACEX, SEHX? NE/polyX
Blank case count: 173 ⊆? NE/polyX? 0

Nearly-P: Languages Superpolynomially Close to P [Yam99]

Nearly-P in the Zoo.

Best inclusions:
∀X: AvgPX, P-CloseXNearly-PXALLX
Best separations:
∃X: CohX, UPX, cocap.NLINX, cocap.beta_2PXNearly-PXNEXP/polyX
Likeliest blank:
∀X: AC^0/polyX, NTX, P-SelX, P/logX, PL_1X, QAC^0X, QCFLX, QNC^0X, cocap.CSLX, cocap.HalfPX, cocap.RNCX, cocap.UPX, cocap.compNPX, polyLX? Nearly-PX
Unlikeliest blank:
∀X: BQP/qpolyX, DQPX, HeurBPPX, PL_{infty}X, QSZKX, cocap.EPX, frIPX? Nearly-PX? CohX
Blank case count: 98 ⊆? Nearly-PX? 1

NEE: Nondeterministic EE

NEE in the Zoo.

Best inclusions:
∀X: NEXPXNEEXEESPACEX, NEEXPX
∀X: EEXcocap.NEEX
Best separations:
∃X: +EXPX, BPEXPX, co.NEXPXNEEXco.NEEXPX
∃X: cocap.NEEXEEXPX
Likeliest blank:
∀X: Almost-PSPACEX, co.QMA(2)X, co.XOR-MIP*[2,1]X, co.frIPX? NEEX
Blank case count: 32 ⊆? NEEX? 0

NEEE: Nondeterministic EEE

NEEE in the Zoo.

Best inclusions:
∀X: NEEXPXNEEEXELEMENTARYX
∀X: EEEXcocap.NEEEX
Best separations:
∃X: co.NEEXPXNEEEX
Likeliest blank:
∀X: co.MIP_{EXP}X? NEEEX
Blank case count: 15 ⊆? NEEEX? 0

NEEXP: Nondeterministic EEXP

NEEXP in the Zoo.

Best inclusions:
∀X: MIP_{EXP}X, NEEXNEEXPXNEEEX
∀X: EEXPXcocap.NEEXPX
Best separations:
∃X: BPEEX, co.NEEXNEEXPXco.NEEEX
∃X: cocap.NEEXPXEEEX
Blank case count: 15 ⊆? NEEXPX? 0

NEXP: Nondeterministic EXP

NEXP in the Zoo.

Best inclusions: [KM02] [KM02]
∀X: NEX, QMIP_{le}X, QMIP_{ne}XNEXPXEXP^{NP}X, MA_{EXP}X, NEEX, NEXP/polyX, SEHX
∀X: EXPX, QRGXcocap.NEXPX
Best separations:
∃X: co.RPEXNEXPXco.NEEX
∃X: cocap.NEXPXBPEEX
Blank case count: 32 ⊆? NEXPX? 2

NEXP/poly: Nonuniform NEXP

NEXP/poly in the Zoo.

Best inclusions:
∀X: EXP/polyX, NE/polyX, NEXPXNEXP/polyXALLX
Best separations:
∃X: +EXPX, AvgEX, CohX, EHX, EXP^{NP}X, Nearly-PX, PL_{infty}XNEXP/polyX
Likeliest blank:
∀X: Almost-PSPACEX, BPQPX, P-SelX, SEHX, cocap.MIP*X? NEXP/polyX
Unlikeliest blank:
∀X: NEXP/polyX? NE/polyX
Blank case count: 29 ⊆? NEXP/polyX? 1

NEXP^{NP}: NEXP with NP oracle

Best inclusions:
∀X: co.AM_{EXP}XNEXP^{NP}XEXPHX
∀X: EXP^{NP}X, MA_{EXP}Xcocap.NEXP^{NP}X
Likeliest blank:
∀X: AM_{EXP}X, EHX? NEXP^{NP}X
Unlikeliest blank:
∀X: EXPHX, MIP_{EXP}X, PEXPX, QPSPACEX? cocap.NEXP^{NP}X
Blank case count: 40 ⊆? NEXP^{NP}X? 2

NIQSZK: Non-Interactive QSZK

NIQSZK in the Zoo.

Best inclusions:
∀X: NISZKXNIQSZKXQSZKX
∀X: BQPXcocap.NIQSZKX
Likeliest blank:
∀X: co.NISZKX, cocap.NISZK_hX, cocap.PZKX? NIQSZKX
∀X: cocap.NIQSZKX? CHX, DQPX, PP/polyX
Unlikeliest blank:
∀X: NIQSZKX? FHX, QAC^0X, QNC_f^0X, TreeBQPX, ZQPX
∀X: NLINSPACEX, NT*X, QX, cocap.N.NISZKX, cocap.QMIPX, cocap.QMIP_{le}X, cocap.QMIP_{ne}X, frIPX? cocap.NIQSZKX
Blank case count: 144 ⊆? NIQSZKX? 272

NISZK: Non-Interactive SZK [DDP+98]

NISZK in the Zoo.

Best inclusions: [BG03]
∀X: NISZKXN.NISZKX, NIQSZKX, NISZK_hX
∀X: BPPXcocap.NISZKX
Likeliest blank:
∀X: NISZKX? co.N.NISZKX, co.NIQSZKX, co.NISZK_hX
∀X: cocap.NISZKX? (NP-cap-coNP)/polyX, BQP/qpolyX, CohX, HeurBPPX, MA_EX, PPX, PZKX, QMA(2)X, QS_2PX, RG[1]X, XOR-MIP*[2,1]X
Unlikeliest blank:
∀X: NISZKX? BPPX
∀X: CZKX, DQPX, QSZKX, polyLX? cocap.NISZKX
Blank case count: 89 ⊆? NISZKX? 222

NISZK_h: NISZK With Limited Help [BG03]

NISZK_h in the Zoo.

Best inclusions: [BG03] [BG03]
∀X: NISZKXNISZK_hXSZKX
Best separations: [Aar02]
∃X: NISZK_hXBQPX
Likeliest blank:
∀X: TreeBQPX, co.NISZKX, cocap.PZKX? NISZK_hX
∀X: cocap.NISZK_hX? N.NISZKX, NIQSZKX
Unlikeliest blank:
∀X: NISZK_hX? cocap.PZKX
∀X: cocap.NISZK_hX? BPPX, QAC^0X, QNC_f^0X, ZQPX
Blank case count: 86 ⊆? NISZK_hX? 221

NL: Nondeterministic Logarithmic-Space

NL in the Zoo.

Best inclusions: [Sud78] [ARZ99]
∀X: LFewX, RLXNLXNL/polyX, SAC^1X, cocap.C_=LX
Blank case count: 33 ⊆? NLX? 30

NL/poly: Nonuniform NL

NL/poly in the Zoo.

Best inclusions: [GW96]
∀X: L/polyX, NLXNL/polyX+L/polyX
Likeliest blank:
∀X: SPLX? NL/polyX
Blank case count: 96 ⊆? NL/polyX? 12

NLIN: Nondeterministic LIN

NLIN in the Zoo.

Best inclusions:
∀X: CFLXNLINXNLINSPACEX, QX
∀X: LINXcocap.NLINX
Best separations:
∃X: cocap.NLINXDQPX, Nearly-PX
Likeliest blank:
∀X: cocap.GCSLX? NLINX? USX, co.A_0PPX, co.NP/polyX, co.QMIPX, co.QMIP_{le}X, co.QMIP_{ne}X, co.RP^{PromiseUP}X
∀X: cocap.NLINX? APPX, AmpMPX, BPQPX, BQP/qpolyX, CZKX, C_=PX, CohX, HeurBPPX, P-SelX, QSZKX, SUBEXPX, XOR-MIP*[2,1]X
Unlikeliest blank:
∀X: betaPX, compIPX? NLINX
∀X: HalfPX, NLINSPACEX, QX, QNCX, cocap.betaPX, cocap.compIPX? cocap.NLINX
Blank case count: 176 ⊆? NLINX? 227

NLINSPACE: Nondeterministic Linear Space

Best inclusions: [Kur64]
∀X: CSLX, NLINX, polyLXNLINSPACEXEX, PSPACEX
Likeliest blank:
∀X: ALX, cocap.QX? NLINSPACEX
Unlikeliest blank:
∀X: NT*X? NLINSPACEX? AVBPPX, BQP/mpolyX, NTX, YQPX, cocap.CZKX, cocap.NIQSZKX, cocap.NLINX, cocap.UPX, cocap.WAPPX, cocap.XOR-MIP*[2,1]X, cocap.beta_2PX, polyLX
Blank case count: 33 ⊆? NLINSPACEX? 173

NONE: The Empty Class

NONE in the Zoo.

Best inclusions:
∀X: NONEXMAJORITYX, NC^0X, PARITYX, TALLYX
Blank case count: 0 ⊆? NONEX? 0

NP: Nondeterministic Polynomial-Time

NP in the Zoo.

Best inclusions: [VV86]
∀X: EPX, QX, RBQPX, betaPX, compNPXNPXN.BPPX, NEX, NP/oneX, RP^{PromiseUP}X, co.USX
∀X: YPXcocap.NPX(NP-cap-coNP)/polyX
Best separations:
∃X: co.RPXNPXC_=PX
Unlikeliest blank:
∀X: NPX? UEX
∀X: cocap.NPX? cocap.UEX
Blank case count: 41 ⊆? NPX? 36

NP/log: NP With Logarithmic Advice

NP/log in the Zoo.

Best inclusions:
∀X: NP/oneXNP/logXNP/polyX
∀X: P/logXcocap.NP/logX
Best separations:
∃X: BQP/qlogX, IC[log,poly]X, P-SelX, SPARSEX, co.SPARSEXNP/logX
Likeliest blank:
∀X: YPPX, co.HalfPX, co.RNCX? NP/logX
Unlikeliest blank:
∀X: NP/logX? NP/oneX
∀X: cocap.NP/logX? cocap.NP/oneX
Blank case count: 188 ⊆? NP/logX? 12

NP/one: NP With One Bit of Advice

Best inclusions:
∀X: NPXNP/oneXNP/logX
∀X: TALLYXcocap.NP/oneX
Best separations: [FFK+93]
∃X: cocap.NP/oneX(NP-cap-coNP)/polyX
Likeliest blank:
∀X: P/logX? NP/oneX
Unlikeliest blank:
∀X: N.NISZKX, NP/logX, QMIPX, QMIP_{le}X, QMIP_{ne}X? NP/oneX
∀X: AVBPPX, BPP//logX, BQP/mlogX, CZKX, DQPX, WAPPX, XOR-MIP*[2,1]X, cocap.N.NISZKX, cocap.NP/logX, cocap.QMIPX, cocap.QMIP_{le}X, cocap.QMIP_{ne}X? cocap.NP/oneX
Blank case count: 193 ⊆? NP/oneX? 8

NP/poly: Nonuniform NP

NP/poly in the Zoo.

Best inclusions: [BM88]
∀X: AMX, N.NISZKX, NP/logXNP/polyXNE/polyX, PP/polyX
∀X: (NP-cap-coNP)/polyXcocap.NP/polyX
Best separations:
∃X: NTX, co.UPX, co.beta_2PX, co.compNPXNP/polyX
Likeliest blank:
∀X: co.NLINX, co.RBQPX, co.WAPPX? NP/polyX
Unlikeliest blank:
∀X: NP/polyX? MIP*X
∀X: cocap.NP/polyX? cocap.MIP*X
Blank case count: 137 ⊆? NP/polyX? 8

NT: Near-Testable [GHJ+91]

NT in the Zoo.

Best inclusions: [GHJ+91] [GHJ+91]
∀X: PXNTXEX, NT*X
Best separations:
∃X: NTXBQP/polyX, DQPX, Mod_3PX, Mod_5PX, NP/polyX, PHX, PPX, SUBEXPX
Likeliest blank:
∀X: NTX? BPQPX, CohX, HeurBPPX, Nearly-PX, P-SelX, PP/polyX, QMIPX, QMIP_{le}X, QMIP_{ne}X, SQGX
Unlikeliest blank:
∀X: EQPX, NLINSPACEX, NT*X, QX, betaPX, cocap.compIPX? NTX
Blank case count: 34 ⊆? NTX? 66

NT*: Near-Testable with Forest Ordering [GHJ+91]

NT* in the Zoo.

Best inclusions: [GHJ+91] [GHJ+91]
∀X: NTXNT*X+PX
Likeliest blank:
∀X: cocap.UPX? NT*X? AvgEX, EHX, NE/polyX
Unlikeliest blank:
∀X: +PX, C_=PX? NT*X? AVBPPX, AvgPX, BPQPX, BQP/mpolyX, CheckX, NLINSPACEX, NTX, cocap.AM[polylog]X, cocap.CZKX, cocap.NIQSZKX, cocap.QAMX, cocap.QMA(2)X, cocap.XOR-MIP*[2,1]X, cocap.compIPX
Blank case count: 52 ⊆? NT*X? 84

P: Polynomial-Time [Edm65] [Cob64] [Rab60]

P in the Zoo.

Best inclusions: [CKS81]
∀X: ALX, LINX, NCX, SCXPXAvgPX, NTX, P-CloseX, P-SelX, P/logX, cocap.HalfPX, cocap.UPX, cocap.beta_2PX, cocap.compNPX
Blank case count: 16 ⊆? PX? 24

P-Close: Problems Close to P

P-Close in the Zoo.

Best inclusions:
∀X: PX, SPARSEXP-CloseXNearly-PX, P/polyX
Unlikeliest blank:
∀X: AVBPPX, AmpP-BQPX, CZKX, FHX, P-SelX, P/polyX, RBQPX, WAPPX, XOR-MIP*[2,1]X, cocap.frIPX? P-CloseX? IC[log,poly]X
Blank case count: 67 ⊆? P-CloseX? 13

P-Sel: P-Selective Sets

P-Sel in the Zoo.

Best inclusions:
∀X: PXP-SelXALLX
Best separations:
∃X: AvgPX, P/logX, TALLYXP-SelXAHX, BQP/logX, NP/logX
Likeliest blank:
∀X: NTX, QAC^0X, QCFLX, QNC^0X, cocap.CSLX, cocap.HalfPX, cocap.NLINX, cocap.RNCX, cocap.UPX, cocap.beta_2PX, cocap.compNPX, polyLX? P-SelX? CohX, NEXP/polyX, Nearly-PX, QMIPX
Unlikeliest blank:
∀X: AVBPPX, Almost-PSPACEX, CohX, DQPX, QMIPX, QMIP_{le}X, QMIP_{ne}X, QPSPACEX, QRGX, SUBEXPX? P-SelX? AC^0/polyX, BPP/mlogX, CohX, IC[log,poly]X, P-CloseX, cocap.MIP*X
Blank case count: 219 ⊆? P-SelX? 32

P/log: P With Logarithmic Advice

P/log in the Zoo.

Best inclusions:
∀X: PXP/logXBPP/logX, IC[log,poly]X, cocap.NP/logX
Best separations:
∃X: ZPPXP/logXAHX, P-SelX
Likeliest blank:
∀X: P/logX? CohX, NP/oneX, Nearly-PX, QMIPX
Unlikeliest blank:
∀X: QX, TALLYX, cocap.betaPX, cocap.compIPX? P/logX
Blank case count: 28 ⊆? P/logX? 17

P/poly: Nonuniform Polynomial-Time

P/poly in the Zoo.

Best inclusions:
∀X: +L/polyX, BPP//logX, IC[log,poly]X, P-CloseX, YPPXP/polyX(NP-cap-coNP)/polyX, BQP/polyX
Best separations: [BV97]
∃X: EQPXP/polyX
Likeliest blank:
∀X: ZBQPX? P/polyX
Unlikeliest blank:
∀X: P/polyX? AC^0/polyX, CohX, P-CloseX
Blank case count: 49 ⊆? P/polyX? 14

P^{#P[1]}: P With Single Query To #P Oracle

P^{#P[1]} in the Zoo.

Best inclusions:
∀X: MPX, PPXP^{#P[1]}XP^{PP}X
Likeliest blank:
∀X: P^{QMA}X? P^{#P[1]}X
Blank case count: 67 ⊆? P^{#P[1]}X? 15

P^{FewP}: P With FewP Oracle

Best inclusions: [FFK94] [Kob89]
∀X: FewXP^{FewP}XDelta_2PX, SPPX
Likeliest blank:
∀X: P^{FewP}X? FewX
Blank case count: 37 ⊆? P^{FewP}X? 16

P^{NP[log]}: P With Log NP Queries

P^{NP[log]} in the Zoo.

Best inclusions: [HHT97]
∀X: BHXP^{NP[log]}XBPP_{path}X, P^{NP[log^2]}X
Best separations: [CS92]
∃X: P^{NP[log^2]}XP^{NP[log]}XBHX
Blank case count: 23 ⊆? P^{NP[log]}X? 12

P^{NP[log^2]}: P With Log^2 NP Queries

P^{NP[log^2]} in the Zoo.

Best inclusions:
∀X: P^{NP[log]}XP^{NP[log^2]}XDelta_2PX
Best separations: [CS92] [CS92]
∃X: Delta_2PXP^{NP[log^2]}XP^{NP[log]}X
Likeliest blank:
∀X: FewX? P^{NP[log^2]}X? PPX
Unlikeliest blank:
∀X: P^{NP[log^2]}X? AWPPX, BPP_{path}X
Blank case count: 23 ⊆? P^{NP[log^2]}X? 14

P^{PP}: P With PP Oracle

P^{PP} in the Zoo.

Best inclusions:
∀X: P^{#P[1]}X, P^{QMA}XP^{PP}XMP^{#P}X
Likeliest open:
∀X: MP^{#P}X? P^{PP}X
Unlikeliest open:
∀X: MP^{#P}X? P^{PP}X
Blank case count: 66 ⊆? P^{PP}X? 15

P^{QMA}: P with QMA Oracle

Best inclusions:
∀X: Delta_2PX, QMAXP^{QMA}XP^{PP}X, QS_2PX
Likeliest blank:
∀X: S_2PX? P^{QMA}X? PP/polyX, P^{#P[1]}X
Unlikeliest blank:
∀X: Almost-PSPACEX, QMIPX, QMIP_{le}X, QMIP_{ne}X, QRGX? P^{QMA}X
Blank case count: 132 ⊆? P^{QMA}X? 29

PARITY: Parity or co-Parity of Input Bits

Best inclusions:
∀X: NONEXPARITYX+SAC^0X, 2-PBPX, PL_1X, REGX
Best separations: [BKL+00] [Smo87]
∃X: PARITYXFOLLX, MAC^0X, QNC^0X, SPARSEX
Likeliest blank:
∀X: PARITYX? AC^0/polyX, QAC^0X
Unlikeliest blank:
∀X: 2-PBPX? PARITYX
Blank case count: 1 ⊆? PARITYX? 2

PBP: Polynomial-Size Branching Program

PBP in the Zoo.

Best inclusions:
∀X: (k>=5)-PBPXPBPXLX, cocap.CSLX
Likeliest blank:
∀X: REGX? PBPX? QNC^1X
Unlikeliest blank:
∀X: PBPX? 3-PBPX, DCFLX
Blank case count: 15 ⊆? PBPX? 30

PEXP: Probabilistic Exponential-Time

PEXP in the Zoo.

Best inclusions: [Ver92]
∀X: MA_{EXP}XPEXPXEXPSPACEX
Best separations: [Ver92]
∃X: cocap.AM_{EXP}XPEXPX
Likeliest blank:
∀X: +EXPX, EHX, EXP^{NP}X, QPSPACEX, SEHX? PEXPX? EXPHX
Unlikeliest blank:
∀X: +EXPX, ESPACEX, EXP^{NP}X, SEHX? PEXPX? NE/polyX, cocap.NEXP^{NP}X
Blank case count: 12 ⊆? PEXPX? 6

PH: Polynomial-Time Hierarchy [Sto76]

PH in the Zoo.

Best inclusions: [Tod89]
∀X: RP^{PromiseUP}X, Sigma_3PXPHXBP.PPX, EHX, MPX
Best separations:
∃X: Mod_3PX, Mod_5PX, NTX, PPXPHX
Unlikeliest blank:
∀X: PHX? cocap.RP^{PromiseUP}X
Blank case count: 91 ⊆? PHX? 14

PL: Probabilistic L

PL in the Zoo.

Best inclusions: [BCP83]
∀X: BPLX, C_=LXPLXL^{DET}X
Likeliest blank:
∀X: L^{DET}X? PLX
Blank case count: 29 ⊆? PLX? 50

PL_1: Polynomially-Bounded L_1 Spectral Norm [BS90]

PL_1 in the Zoo.

Best inclusions:
∀X: NC^0X, PARITYX, SPARSEXPL_1XPT_1X
Best separations:
∃X: MAJORITYXPL_1X
Likeliest blank:
∀X: PL_1X? Nearly-PX
Unlikeliest blank:
∀X: 4-PBPX, SAC^0X? PL_1X
Blank case count: 7 ⊆? PL_1X? 11

PL_{infty}: Polynomially-Bounded L_{infty}^{-1} Spectral Norm [BS90]

PL_{infty} in the Zoo.

Best inclusions: [BS90]
∀X: PT_1XPL_{infty}XALLX
Best separations: [BS90]
∃X: (k>=5)-PBPX, +SAC^0X, AC^0X, REGXPL_{infty}XNEXP/polyX
Likeliest blank:
∀X: 2-PBPX, QNC^0X, cocap.SAC^0X? PL_{infty}X
Unlikeliest blank:
∀X: PL_{infty}X? CohX, Nearly-PX, cocap.MIP*X
Blank case count: 7 ⊆? PL_{infty}X? 8

polyL: Polylogarithmic Space

polyL in the Zoo.

Best inclusions: [Bor77]
∀X: NCX, SCXpolyLXNLINSPACEX, QPX
Best separations:
∃X: polyLXBQP/polyX, CohX
Likeliest blank:
∀X: LINX? polyLX? CHX, DQPX, HeurBPPX, Nearly-PX, P-SelX, PP/polyX, QMIPX, QMIP_{le}X, QMIP_{ne}X, QPLINX, SQGX
Unlikeliest blank:
∀X: EQPX, NLINSPACEX, QX, betaPX, cocap.compIPX? polyLX? AvgPX, cocap.NISZKX, cocap.PZKX
Blank case count: 35 ⊆? polyLX? 182

PP: Probabilistic Polynomial-Time

PP in the Zoo.

Best inclusions: [Vya03] [HHT97]
∀X: APPX, A_0PPX, BPP_{path}XPPXBP.PPX, P^{#P[1]}X
Best separations: [Bei94] [Ver92]
∃X: Delta_2PX, NTX, cocap.AMXPPXPHX
Likeliest blank:
∀X: P^{NP[log^2]}X, cocap.NISZKX, cocap.PZKX, cocap.RP^{PromiseUP}X? PPX
Unlikeliest blank:
∀X: PPX? AWPPX
Blank case count: 46 ⊆? PPX? 18

PP/poly: Nonuniform PP

PP/poly in the Zoo.

Best inclusions: [Aar04b]
∀X: BP.PPX, BQP/qpolyX, NP/polyXPP/polyXEXP/polyX
Best separations:
∃X: AvgPXPP/polyX
Likeliest blank:
∀X: AVBPPX, Mod_3PX, Mod_5PX, NTX, P^{QMA}X, QPLINX, RG[1]X, cocap.AM[polylog]X, cocap.CSLX, cocap.CZKX, cocap.NIQSZKX, cocap.compIPX, polyLX? PP/polyX
Likeliest open:
∀X: DQPX? PP/polyX
Unlikeliest blank:
∀X: QPSPACEX? PP/polyX
Unlikeliest open:
∀X: DQPX? PP/polyX
Blank case count: 82 ⊆? PP/polyX? 1

PR: Primitive Recursive Functions

PR in the Zoo.

Best inclusions:
∀X: ELEMENTARYXPRXRX
Best separations: [HS65] [HS65]
∃X: RXPRXELEMENTARYX
Blank case count: 6 ⊆? PRX? 0

PSPACE: Polynomial-Space

PSPACE in the Zoo.

Best inclusions: [Wat02] [FK97b]
∀X: CHX, IPX, NLINSPACEX, QSZKX, RG[1]XPSPACEXAlmost-PSPACEX, QPSPACEX, RGX
Blank case count: 37 ⊆? PSPACEX? 15

PT_1: Polynomial Threshold Functions [BS90]

PT_1 in the Zoo.

Best inclusions: [BS90] [Bru90]
∀X: MAJORITYX, PL_1XPT_1XPL_{infty}X, TC^0/polyX
Blank case count: 7 ⊆? PT_1X? 11

PZK: Perfect Zero Knowledge

PZK in the Zoo.

Best inclusions:
∀X: PZKXSZKX
∀X: BPPXcocap.PZKX
Likeliest blank:
∀X: cocap.NISZKX? PZKX? (NP-cap-coNP)/polyX
∀X: cocap.PZKX? BQP/qpolyX, CohX, HeurBPPX, MA_EX, N.NISZKX, NIQSZKX, NISZK_hX, PPX, QMA(2)X, QS_2PX, RG[1]X, XOR-MIP*[2,1]X
Likeliest open:
∀X: PZKX? co.PZKX
∀X: cocap.PZKX? (NP-cap-coNP)/polyX
Unlikeliest blank:
∀X: PZKX? BPPX, QAC^0X, QNC_f^0X, ZQPX
∀X: CZKX, NISZK_hX, QSZKX, RQPX, polyLX? cocap.PZKX
Unlikeliest open:
∀X: PZKX? co.PZKX
∀X: cocap.PZKX? (NP-cap-coNP)/polyX
Blank case count: 76 ⊆? PZKX? 231

Q: Quasi-Realtime Languages [BG69]

Q in the Zoo.

Best inclusions: [DW86]
∀X: GCSLX, NLINXQXEX, NPX
Likeliest blank:
∀X: 2-PBPX, NC^0X, co.CFLX, cocap.1NAuxPDA^pX? QX
∀X: cocap.QX? NLINSPACEX
Unlikeliest blank:
∀X: QX? AC^0/polyX, AVBPPX, CheckX, NTX, P/logX, YPX, cocap.CZKX, cocap.NIQSZKX, cocap.NLINX, cocap.UPX, cocap.WAPPX, cocap.XOR-MIP*[2,1]X, cocap.beta_2PX, cocap.compNPX, polyLX
Blank case count: 170 ⊆? QX? 233

QAC^0: Quantum AC^0 [Moo99]

QAC^0 in the Zoo.

Best inclusions:
∀X: AC^0XQAC^0XQACC^0X
Likeliest blank:
∀X: PARITYX, QNC^0X? QAC^0X? AvgEX, C_=PX, CohX, EHX, FHX, HeurBPPX, MIPX, MIP*X, MPX, NE/polyX, Nearly-PX, P-SelX, RG[1]X, RQPX, SF_4X
Unlikeliest blank:
∀X: AVBPPX, CSLX, CheckX, NIQSZKX, PZKX, WAPPX, XOR-MIP*[2,1]X, cocap.NISZK_hX? QAC^0X? +SAC^0X, AC^0X
Blank case count: 109 ⊆? QAC^0X? 248

QACC^0: Quantum ACC^0 [Moo99]

QACC^0 in the Zoo.

Best inclusions:
∀X: ACC^0X, QAC^0X, QNC_f^0XQACC^0XQNC^1X
Likeliest blank:
∀X: MAJORITYX, REGX? QACC^0X
Blank case count: 99 ⊆? QACC^0X? 244

QAM: Quantum AM [MW05]

QAM in the Zoo.

Best inclusions: [MW05]
∀X: AMX, QMAXQAMXBP.PPX, QIP[2]X
Likeliest blank:
∀X: cocap.QAMX? MP^{#P}X
Unlikeliest blank:
∀X: QMIPX, QMIP_{le}X, QMIP_{ne}X? QAMX
∀X: NT*X? cocap.QAMX
Blank case count: 95 ⊆? QAMX? 109

QCFL: Quantum CFL [MC00]

QCFL in the Zoo.

Best inclusions:
∀X: CFLXQCFLXBQPX
Best separations: [MC00]
∃X: +SAC^0X, LINX, SAC^0XQCFLXCFLX
Likeliest blank:
∀X: 2-PBPX, NC^0X, cocap.1NAuxPDA^pX, cocap.GCSLX? QCFLX? AvgEX, C_=PX, CohX, EHX, FHX, HeurBPPX, MIPX, MIP*X, MPX, NE/polyX, Nearly-PX, P-SelX, QNCX, RG[1]X, RQPX, SF_4X
Unlikeliest blank:
∀X: QCFLX? 3-PBPX, AC^0/polyX, LINX, cocap.1NAuxPDA^pX, cocap.GCSLX
Blank case count: 17 ⊆? QCFLX? 257

QCMA: Quantum Classical MA [AN02]

QCMA in the Zoo.

Best inclusions:
∀X: MAXQCMAXQMAX
∀X: BQPXcocap.QCMAX
Likeliest blank:
∀X: YQPX? QCMAX
Unlikeliest blank:
∀X: SBPX? QCMAX
∀X: DQPX, QSZKX, YQPX, frIPX? cocap.QCMAX
Blank case count: 91 ⊆? QCMAX? 121

QIP: Quantum IP [Wat99]

QIP in the Zoo.

Best inclusions: [GW05]
∀X: IPX, QIP[2]XQIPXQMIPX, QMIP_{le}X, QMIP_{ne}X, SQGX
Blank case count: 69 ⊆? QIPX? 131

QIP[2]: 2-Message Quantum IP [Wat99]

QIP[2] in the Zoo.

Best inclusions:
∀X: QAMXQIP[2]XQIPX
∀X: QSZKXcocap.QIP[2]X
Likeliest blank:
∀X: cocap.AM[polylog]X, cocap.CZKX, cocap.compIPX? QIP[2]X
∀X: cocap.QIP[2]X? Almost-PSPACEX, ESPACEX, RGX
Unlikeliest blank:
∀X: QIP[2]X? AMX
Blank case count: 84 ⊆? QIP[2]X? 129

QMA: Quantum MA [Wat00]

QMA in the Zoo.

Best inclusions: [Vya03]
∀X: QCMAXQMAXA_0PPX, P^{QMA}X, QAMX, QMA(2)X
∀X: YQPXcocap.QMAX
Unlikeliest blank:
∀X: cocap.QMA(2)X? cocap.QMAX
Blank case count: 91 ⊆? QMAX? 121

QMA(2): Quantum MA With Multiple Certificates [KMY01]

QMA(2) in the Zoo.

Best inclusions:
∀X: QMAXQMA(2)XQMIP_{ne}X
Likeliest blank:
∀X: CheckX, cocap.NISZKX, cocap.PZKX, cocap.WAPPX, cocap.compIPX? QMA(2)X? co.MIP_{EXP}X, co.NEEX
∀X: cocap.QMA(2)X? +EXPX, BPEEX, EXP/polyX, QMIPX, QMIP_{le}X, QRGX
Unlikeliest blank:
∀X: QMIPX, QMIP_{le}X, QMIP_{ne}X? QMA(2)X? N.NISZKX, S_2PX, WAPPX, co.C_=PX
∀X: NT*X, cocap.QMIPX, cocap.QMIP_{le}X, cocap.QMIP_{ne}X? cocap.QMA(2)X? cocap.C_=PX, cocap.QMAX, cocap.WAPPX
Blank case count: 126 ⊆? QMA(2)X? 204

QMIP: Quantum Multi-Prover Interactive Proofs [KM02]

QMIP in the Zoo.

Best inclusions:
∀X: MIP*X, QIPXQMIPXALLX
Best separations:
∃X: AvgPX, co.UPX, co.beta_2PXQMIPX
Likeliest blank:
∀X: AVBPPX, CheckX, NTX, P-SelX, P/logX, TALLYX, co.CZKX, co.NLINX, co.TALLYX, co.WAPPX, co.XOR-MIP*[2,1]X, co.compNPX, cocap.CSLX, cocap.N.NISZKX, cocap.QMA(2)X, cocap.QMIP_{le}X, polyLX? QMIPX
Likeliest open:
∀X: DQPX? QMIPX
Unlikeliest blank:
∀X: QMIPX? IPX, MA_EX, ModPX, NP/oneX, P-SelX, P^{QMA}X, QAMX, QMA(2)X, RG[1]X, SF_2X, XOR-MIP*[2,1]X, co.RP^{NP}X, cocap.RP^{PromiseUP}X
∀X: cocap.QMIPX? (NP-cap-coNP)/polyX, S_2PX, cocap.AMX, cocap.MA_EX, cocap.N.NISZKX, cocap.NIQSZKX, cocap.NP/oneX, cocap.QMA(2)X, cocap.XOR-MIP*[2,1]X
Unlikeliest open:
∀X: DQPX? QMIPX
Blank case count: 127 ⊆? QMIPX? 243

QMIP_{le}: Quantum Multi-Prover Interactive Proofs With Limited Prior Entanglement [KM02]

QMIP_{le} in the Zoo.

Best inclusions: [KM02] [CHT+04]
∀X: QIPX, XOR-MIP*[2,1]XQMIP_{le}XNEXPX
Best separations:
∃X: AvgPX, co.UPX, co.beta_2PXQMIP_{le}X
Likeliest blank:
∀X: AVBPPX, CheckX, NTX, co.CZKX, co.NLINX, co.WAPPX, co.compNPX, cocap.CSLX, cocap.N.NISZKX, cocap.QMA(2)X, polyLX? QMIP_{le}X
∀X: cocap.QMIP_{le}X? QMIPX
Likeliest open:
∀X: DQPX? QMIP_{le}X
Unlikeliest blank:
∀X: QMIP_{le}X? IPX, MA_EX, ModPX, NP/oneX, P-SelX, P^{QMA}X, QAMX, QMA(2)X, RG[1]X, SF_2X, XOR-MIP*[2,1]X, co.RP^{NP}X, cocap.RP^{PromiseUP}X
∀X: cocap.QMIP_{le}X? (NP-cap-coNP)/polyX, S_2PX, cocap.AMX, cocap.MA_EX, cocap.N.NISZKX, cocap.NIQSZKX, cocap.NP/oneX, cocap.QMA(2)X, cocap.XOR-MIP*[2,1]X
Unlikeliest open:
∀X: DQPX? QMIP_{le}X
Blank case count: 63 ⊆? QMIP_{le}X? 171

QMIP_{ne}: Quantum Multi-Prover Interactive Proofs With No Prior Entanglement [KM02]

QMIP_{ne} in the Zoo.

Best inclusions: [KM02]
∀X: MIPX, QIPX, QMA(2)XQMIP_{ne}XNEXPX
Best separations:
∃X: AvgPX, co.UPX, co.beta_2PXQMIP_{ne}X
Likeliest blank:
∀X: AVBPPX, NTX, co.CZKX, co.NLINX, co.WAPPX, co.compNPX, cocap.CSLX, cocap.N.NISZKX, cocap.XOR-MIP*[2,1]X, polyLX? QMIP_{ne}X
Likeliest open:
∀X: DQPX? QMIP_{ne}X
Unlikeliest blank:
∀X: QMIP_{ne}X? IPX, MA_EX, ModPX, NP/oneX, P-SelX, P^{QMA}X, QAMX, QMA(2)X, RG[1]X, SF_2X, XOR-MIP*[2,1]X, co.RP^{NP}X, cocap.RP^{PromiseUP}X
∀X: cocap.QMIP_{ne}X? (NP-cap-coNP)/polyX, S_2PX, cocap.AMX, cocap.MA_EX, cocap.N.NISZKX, cocap.NIQSZKX, cocap.NP/oneX, cocap.QMA(2)X, cocap.XOR-MIP*[2,1]X
Unlikeliest open:
∀X: DQPX? QMIP_{ne}X
Blank case count: 55 ⊆? QMIP_{ne}X? 171

QNC: Quantum NC

QNC in the Zoo.

Best inclusions:
∀X: QNC^1X, RNCXQNCXBQPX
Likeliest blank:
∀X: ALX, LINX, QCFLX, SCX? QNCX
Unlikeliest blank:
∀X: QNCX? AC^0/polyX, ALX, NCX, SCX, cocap.NLINX
Blank case count: 44 ⊆? QNCX? 208

QNC^0: Quantum NC^0 [Spa02]

QNC^0 in the Zoo.

Best inclusions:
∀X: NC^0XQNC^0XQNC_f^0X
Best separations:
∃X: MAJORITYX, PARITYX, SAC^0XQNC^0X
Likeliest blank:
∀X: QNC^0X? AvgEX, C_=PX, CohX, EHX, FHX, HeurBPPX, MIPX, MIP*X, MPX, NE/polyX, Nearly-PX, P-SelX, PL_{infty}X, QAC^0X, RG[1]X, RQPX, SF_4X
Unlikeliest blank:
∀X: QNC^0X? 3-PBPX, MAJORITYX, NC^0X, REGX
Blank case count: 1 ⊆? QNC^0X? 272

QNC^1: Quantum NC^1

QNC^1 in the Zoo.

Best inclusions:
∀X: NC^1X, QACC^0XQNC^1XQNCX
Likeliest blank:
∀X: DCFLX, FOLLX, PBPX? QNC^1X
Unlikeliest blank:
∀X: QNC^1X? ACC^0X, LINX, cocap.1NAuxPDA^pX
Blank case count: 92 ⊆? QNC^1X? 245

QNC_f^0: Quantum NC^0 With Unbounded Fanout [Spa02]

QNC_f^0 in the Zoo.

Best inclusions: [Moo99]
∀X: +SAC^0X, QNC^0XQNC_f^0XQACC^0X
Likeliest blank:
∀X: 2-PBPX, cocap.SAC^0X? QNC_f^0X
Unlikeliest blank:
∀X: AVBPPX, CSLX, CheckX, NIQSZKX, PZKX, WAPPX, XOR-MIP*[2,1]X, cocap.NISZK_hX? QNC_f^0X? +SAC^0X
Blank case count: 110 ⊆? QNC_f^0X? 245

QP: Quasipolynomial-Time

QP in the Zoo.

Best inclusions:
∀X: QPLINX, betaPX, polyLXQPXBPQPX, SUBEXPX
Blank case count: 26 ⊆? QPX? 10

QPLIN: Linear Quasipolynomial-Time

QPLIN in the Zoo.

Best inclusions:
∀X: beta_2PXQPLINXQPX
Best separations:
∃X: cocap.betaPXQPLINXAlmost-PSPACEX, BQP/logX
Likeliest blank:
∀X: polyLX? QPLINX? PP/polyX, QRGX
Unlikeliest blank:
∀X: EQPX? QPLINX? BQP/mlogX
Blank case count: 27 ⊆? QPLINX? 13

QPSPACE: Quasipolynomial-Space

QPSPACE in the Zoo.

Best inclusions:
∀X: BPQPX, PSPACEXQPSPACEXESPACEX
Best separations:
∃X: AvgPX, SUBEXPXQPSPACEXMIP_{EXP}X, SEHX
Likeliest blank:
∀X: QPSPACEX? EXPHX, PEXPX
Unlikeliest blank:
∀X: QPSPACEX? EHX, NE/polyX, P-SelX, PP/polyX, cocap.NEXP^{NP}X
Blank case count: 37 ⊆? QPSPACEX? 11

QRG: Quantum Refereed Games [Gut05]

QRG in the Zoo.

Best inclusions:
∀X: RGX, SQGXQRGXcocap.NEXPX
Best separations:
∃X: AvgPXQRGX
Likeliest blank:
∀X: AVBPPX, CheckX, QPLINX, cocap.QMA(2)X, cocap.XOR-MIP*[2,1]X? QRGX? +EXPX, BPEEX, EXP/polyX
Likeliest open:
∀X: DQPX? QRGX
Unlikeliest blank:
∀X: QRGX? BP.PPX, EHX, ModPX, P-SelX, P^{QMA}X, RG[1]X, SF_2X
Unlikeliest open:
∀X: DQPX? QRGX
Blank case count: 30 ⊆? QRGX? 30

QS_2P: Quantum S_2P

QS_2P in the Zoo.

Best inclusions:
∀X: P^{QMA}X, S_2PXQS_2PXSQGX
Likeliest blank:
∀X: RG[1]X, cocap.NISZKX, cocap.PZKX, cocap.WAPPX, cocap.compIPX? QS_2PX? Almost-PSPACEX, ESPACEX, RGX
Unlikeliest blank:
∀X: SUBEXPX? QS_2PX? S_2PX
Blank case count: 133 ⊆? QS_2PX? 38

QSZK: Quantum Statistical Zero-Knowledge [Wat02]

QSZK in the Zoo.

Best inclusions: [Wat02]
∀X: NIQSZKX, SZKXQSZKXPSPACEX, cocap.QIP[2]X
Likeliest blank:
∀X: YPX, cocap.NLINX, cocap.UPX, cocap.WAPPX, cocap.beta_2PX, cocap.compNPX? QSZKX
Unlikeliest blank:
∀X: QSZKX? AVBPPX, AvgEX, BPQPX, BQP/logX, Nearly-PX, YQPX, cocap.C_=PX, cocap.NISZKX, cocap.PZKX, cocap.QCMAX, cocap.WAPPX
Blank case count: 60 ⊆? QSZKX? 126

R: Recursive Languages

R in the Zoo.

Best inclusions:
∀X: PRXRXREX
Best separations: [HS65]
∃X: RXPRX
Blank case count: 6 ⊆? RX? 0

R_HL: Randomized Halting Logarithmic-Space

R_HL in the Zoo.

Best inclusions:
∀X: R_HLXRLX
∀X: LXcocap.R_HLX
Likeliest blank:
∀X: cocap.RLX? R_HLX? co.RLX
∀X: cocap.R_HLX? +LX
Unlikeliest blank:
∀X: CSLX? cocap.R_HLX
Blank case count: 99 ⊆? R_HLX? 68

RBQP: Strict Quantum RP

RBQP in the Zoo.

Best inclusions:
∀X: RPXRBQPXNPX, RQPX
∀X: ZBQPXRBQPX
Likeliest blank:
∀X: RBQPX? co.MA_EX, co.MIPX, co.MIP*X, co.NP/polyX
∀X: ZBQPX? AmpP-BQPX, BPEX, CZKX, CohX, FHX, HeurBPPX, P/polyX, WAPPX, XOR-MIP*[2,1]X
Unlikeliest blank:
∀X: RBQPX? AC^0/polyX, IC[log,poly]X, P-CloseX, RNCX, YPPX, cocap.compIPX, compNPX
∀X: ZBQPX? cocap.RNCX, cocap.compNPX
Blank case count: 26 ⊆? RBQPX? 182

RE: Recursively Enumerable Languages

RE in the Zoo.

Best inclusions:
∀X: REXAHX
∀X: PRXRXREX
Best separations: [Tur36] [HS65]
∃X: REXco.REX
∃X: RXPRX
Blank case count: 12 ⊆? REX? 0

REG: Regular Languages

REG in the Zoo.

Best inclusions:
∀X: PARITYXREGXDCFLX, NC^1X
Best separations: [GG66]
∃X: DCFLX, MAJORITYXREGX2-PBPX, PL_{infty}X
Likeliest blank:
∀X: REGX? PBPX, QACC^0X, TC^0/polyX
Unlikeliest blank:
∀X: 4-PBPX, QNC^0X, cocap.SAC^0X? REGX
Blank case count: 6 ⊆? REGX? 13

RG: Refereed Games

RG in the Zoo.

Best inclusions: [KM92]
∀X: PSPACEXRGXEXPX, QRGX
Likeliest blank:
∀X: QS_2PX, cocap.QIP[2]X? RGX? Almost-PSPACEX, ESPACEX
Unlikeliest blank:
∀X: SUBEXPX? RGX
Blank case count: 39 ⊆? RGX? 23

RG[1]: One-Round Refereed Games

RG[1] in the Zoo.

Best inclusions: [FK97b]
∀X: S_2PXRG[1]XPSPACEX, SQGX
Likeliest blank:
∀X: EQPX, FHX, QAC^0X, QCFLX, QNC^0X, TreeBQPX, cocap.NISZKX, cocap.PZKX, cocap.WAPPX, cocap.compIPX? RG[1]X? CHX, EHX, PP/polyX, QS_2PX
Unlikeliest blank:
∀X: Almost-PSPACEX, QMIPX, QMIP_{le}X, QMIP_{ne}X, QRGX? RG[1]X? S_2PX
Blank case count: 153 ⊆? RG[1]X? 33

RL: Randomized Logarithmic-Space

RL in the Zoo.

Best inclusions:
∀X: R_HLXRLXBPLX, NLX
Likeliest blank:
∀X: co.R_HLX? RLX
∀X: cocap.RLX? R_HLX
Blank case count: 96 ⊆? RLX? 72

RNC: Randomized NC

RNC in the Zoo.

Best inclusions:
∀X: RNCXQNCX, RPX
∀X: NCXcocap.RNCX
Likeliest blank:
∀X: RNCX? USX, YPPX, co.NEX, co.NP/logX, co.RP^{PromiseUP}X, co.RQPX
∀X: cocap.RNCX? AmpMPX, AvgEX, C_=PX, IC[log,poly]X, Nearly-PX, P-SelX, UEX, compIPX
Unlikeliest blank:
∀X: RBQPX? RNCX
∀X: ZBQPX? cocap.RNCX
Blank case count: 43 ⊆? RNCX? 176

RP: Randomized Polynomial-Time

RP in the Zoo.

Best inclusions:
∀X: HalfPX, RNCXRPXBPPX, RBQPX, RPEX
∀X: ZPPXRPX, YPX
Best separations: [BBF98] [BBF98] [STT05]
∃X: RPXco.NPX
∃X: ZPPX+PX, EX, Mod_3PX, Mod_5PX, P/logX, WPPX
Blank case count: 29 ⊆? RPX? 75

RP^{NP}: RP With NP Oracle

Best inclusions: [Cai01]
∀X: RP^{NP}XBPP^{NP}X, Sigma_2PX
∀X: S_2PX, cocap.AMXZPP^{NP}XRP^{NP}X
Likeliest blank:
∀X: co.WAPPX? RP^{NP}X? co.Sigma_2PX
Unlikeliest blank:
∀X: Sigma_2PX, co.QMIPX, co.QMIP_{le}X, co.QMIP_{ne}X? RP^{NP}X? S_2PX
∀X: cocap.Sigma_2PX? ZPP^{NP}X
Blank case count: 161 ⊆? RP^{NP}X? 32

RP^{PromiseUP}: RP With Promise UP Oracle

Best inclusions: [VV86]
∀X: NPXRP^{PromiseUP}XPHX
∀X: UPXcocap.RP^{PromiseUP}X
Likeliest blank:
∀X: YPPX, co.FewPX, co.HalfPX, co.NLINX, co.RNCX, co.beta_2PX, co.compNPX, cocap.USX? RP^{PromiseUP}X
∀X: cocap.RP^{PromiseUP}X? NE/polyX, PPX, SF_4X, SQGX, Sigma_3PX
Unlikeliest blank:
∀X: RP^{PromiseUP}X? AWPPX, co.C_=PX, cocap.USX
∀X: APPX, AVBPPX, A_0PPX, DQPX, PHX, QMIPX, QMIP_{le}X, QMIP_{ne}X, SQGX? cocap.RP^{PromiseUP}X? cocap.C_=PX
Blank case count: 337 ⊆? RP^{PromiseUP}X? 82

RPE: Randomized E

Best inclusions:
∀X: RPXRPEXBPEX, NEX
∀X: EXZPEXRPEX
Best separations:
∃X: RPEXco.NEXPX
∃X: ZPEX+EXPX, EXP/polyX
Unlikeliest blank:
∀X: RQPX, YPPX? ZPEX
Blank case count: 55 ⊆? RPEX? 2

RQP: One-sided Error Extension of EQP

RQP in the Zoo.

Best inclusions:
∀X: RBQPXRQPXBQPX
∀X: EQPXZQPXRQPX
Likeliest blank:
∀X: QAC^0X, QCFLX, QNC^0X, co.RNCX? RQPX
Unlikeliest blank:
∀X: RQPX? TreeBQPX, ZPEX, cocap.N.BPPX, cocap.PZKX, cocap.UEX
∀X: AVBPPX, CheckX, NIQSZKX, PZKX, WAPPX, XOR-MIP*[2,1]X, cocap.NISZK_hX? ZQPX
Blank case count: 78 ⊆? RQPX? 226

S_2P: Second Level of the Symmetric Hierarchy [RS98]

S_2P in the Zoo.

Best inclusions: [Cai01] [RS98] [RS98]
∀X: Delta_2PX, MAXS_2PXQS_2PX, RG[1]X, ZPP^{NP}X
Best separations:
∃X: cocap.Sigma_2PXS_2PX
Likeliest blank:
∀X: S_2PX? P^{QMA}X
Unlikeliest blank:
∀X: C_=PX, DQPX, QMA(2)X, QS_2PX, RG[1]X, RP^{NP}X, cocap.QMIPX, cocap.QMIP_{le}X, cocap.QMIP_{ne}X? S_2PX
Blank case count: 91 ⊆? S_2PX? 11

SAC^0: Semi-Unbounded-Fanin AC^0 [BCD+89]

SAC^0 in the Zoo.

Best inclusions:
∀X: SAC^0XAC^0X
∀X: NC^0Xcocap.SAC^0X
Best separations: [BCD+89]
∃X: SAC^0XCSLX, QCFLX, QNC^0X, co.SAC^0X
Likeliest blank:
∀X: cocap.SAC^0X? PL_{infty}X, QNC_f^0X
Unlikeliest blank:
∀X: SAC^0X? PL_1X, co.GCSLX
∀X: cocap.SAC^0X? 3-PBPX, MAJORITYX, NC^0X, REGX
Blank case count: 2 ⊆? SAC^0X? 51

SAC^1: Semi-Unbounded-Fanin AC^1 [BCD+89]

SAC^1 in the Zoo.

Best inclusions: [GW96] [Bra77] [DW86] [Sud78]
∀X: 1NAuxPDA^pX, GCSLX, NLXSAC^1X+SAC^1X, AC^1X
Likeliest blank:
∀X: SPLX? SAC^1X
Blank case count: 22 ⊆? SAC^1X? 50

SBP: Small Bounded-Error Probability [BGM02]

SBP in the Zoo.

Best inclusions: [BGM02] [BGM02] [BGM02] [BGM02]
∀X: MAX, WAPPXSBPXAMX, BPP_{path}X
Likeliest blank:
∀X: cocap.SBPX? A_0PPX
Unlikeliest blank:
∀X: SBPX? QCMAX, WAPPX, co.C_=PX
∀X: cocap.SBPX? cocap.C_=PX, cocap.N.BPPX, cocap.WAPPX
Blank case count: 115 ⊆? SBPX? 86

SC: Steve's Class

SC in the Zoo.

Best inclusions: [Nis92] [Coo79]
∀X: BPLX, DCFLXSCXPX, polyLX
Likeliest blank:
∀X: FOLLX, cocap.CFLX, cocap.ULX? SCX? QNCX
Unlikeliest blank:
∀X: HalfPX, QNCX? SCX? ACC^0X, cocap.1NAuxPDA^pX
Blank case count: 53 ⊆? SCX? 58

SEH: Strong Exponential Hierarchy

SEH in the Zoo.

Best inclusions:
∀X: NEXPXSEHXEXPSPACEX
Best separations: [Hem89]
∃X: +EXPX, BPEX, QPSPACEXSEHXEXPHX
Likeliest blank:
∀X: Almost-PSPACEX, BPQPX, EXP^{NP}X? SEHX? NEXP/polyX, PEXPX
Unlikeliest blank:
∀X: BPQPX, EXP^{NP}X? SEHX? NE/polyX, PEXPX
Blank case count: 9 ⊆? SEHX? 3

SF_2: Width-2 Bottleneck Turing Machines [CF91]

Best inclusions: [Ogi94]
∀X: +PX, Delta_2PXSF_2XSF_3X
Likeliest blank:
∀X: Mod_3PX? SF_2X? MP^{#P}X
Unlikeliest blank:
∀X: AVBPPX, Almost-PSPACEX, DQPX, QMIPX, QMIP_{le}X, QMIP_{ne}X, QRGX? SF_2X
Blank case count: 157 ⊆? SF_2X? 15

SF_3: Width-3 Bottleneck Turing Machines [CF91]

Best inclusions:
∀X: Mod_3PX, SF_2XSF_3XSF_4X
Likeliest blank:
∀X: SF_4X? SF_3X
Blank case count: 155 ⊆? SF_3X? 16

SF_4: Width-4 Bottleneck Turing Machines [CF91]

Best inclusions: [Ogi94] [Her97]
∀X: SF_3XSF_4XCHX
Likeliest blank:
∀X: BPPX, EQPX, Mod_5PX, QAC^0X, QCFLX, QNC^0X, YPPX, cocap.RP^{PromiseUP}X? SF_4X? SF_3X
Blank case count: 154 ⊆? SF_4X? 17

Sigma_2P: NP With NP Oracle

Sigma_2P in the Zoo.

Best inclusions:
∀X: N.NISZKX, RP^{NP}X, co.AMXSigma_2PXDelta_3PX, SQGX
Best separations: [BGM02]
∃X: WAPPXSigma_2PX
∃X: cocap.Sigma_2PXS_2PX
Likeliest blank:
∀X: co.N.NISZKX, co.RP^{NP}X? Sigma_2PX
Unlikeliest blank:
∀X: Sigma_2PX? RP^{NP}X
∀X: cocap.Sigma_2PX? ZPP^{NP}X
Blank case count: 152 ⊆? Sigma_2PX? 32

Sigma_3P: NP With Sigma_2P Oracle

Best inclusions:
∀X: Sigma_3PXPHX
∀X: AmpP-BQPX, Delta_3PXcocap.Sigma_3PX
Best separations: [Yao85] [Yao85]
∃X: Sigma_3PXco.Sigma_3PX
∃X: cocap.Sigma_3PXDelta_3PX
Likeliest blank:
∀X: cocap.RP^{PromiseUP}X? Sigma_3PX
Blank case count: 188 ⊆? Sigma_3PX? 28

SPARSE: Sparse Languages

SPARSE in the Zoo.

Best inclusions:
∀X: TALLYXSPARSEXAC^0/polyX, P-CloseX, PL_1X
∀X: NONEXMAJORITYX, NC^0X, PARITYX, TALLYX
Best separations:
∃X: NC^0X, PARITYX, co.TALLYXSPARSEXBPP//logX, BQP/qlogX, NP/logX, co.NP/logX
Blank case count: 0 ⊆? SPARSEX? 8

SPL: Stoic PL

SPL in the Zoo.

Best inclusions: [ARZ99]
∀X: LFewXSPLX+LX, cocap.C_=LX
Likeliest blank:
∀X: SPLX? NL/polyX, SAC^1X
Likeliest open:
∀X: SPLX? AC^1X
Unlikeliest blank:
∀X: NC^2X? SPLX
Unlikeliest open:
∀X: SPLX? AC^1X
Blank case count: 41 ⊆? SPLX? 42

SPP: Stoic PP [FFK94]

SPP in the Zoo.

Best inclusions: [FFK94] [NR98]
∀X: P^{FewP}X, UAPXSPPX+PX, LWPPX, Mod_3PX, Mod_5PX
Unlikeliest blank:
∀X: SPPX? FewX, cocap.USX
Blank case count: 37 ⊆? SPPX? 36

SQG: Short Quantum Games [GW05]

SQG in the Zoo.

Best inclusions: [Gut05] [GW05]
∀X: BPP^{NP}X, QIPX, QS_2PX, RG[1]X, Sigma_2PXSQGXEXPX, QRGX
Likeliest blank:
∀X: Delta_3PX, NTX, UAPX, cocap.CSLX, cocap.RP^{PromiseUP}X, polyLX? SQGX
Unlikeliest blank:
∀X: SQGX? BPP^{NP}X, cocap.RP^{PromiseUP}X
Blank case count: 75 ⊆? SQGX? 32

SUBEXP: Deterministic Subexponential-Time

SUBEXP in the Zoo.

Best inclusions:
∀X: QPXSUBEXPXEX
Best separations:
∃X: AvgPX, NTX, compNPXSUBEXPXQPSPACEX
Likeliest blank:
∀X: cocap.CSLX, cocap.NLINX? SUBEXPX
Unlikeliest blank:
∀X: SUBEXPX? AVBPPX, BQP/mpolyX, P-SelX, QS_2PX, RGX
Blank case count: 26 ⊆? SUBEXPX? 10

SZK: Statistical Zero Knowledge

SZK in the Zoo.

Best inclusions: [Aar02b] [BG03]
∀X: NISZK_hX, PZKXSZKXDQPX, QSZKX, cocap.AMX, cocap.CZKX
Blank case count: 32 ⊆? SZKX? 103

TALLY: Tally Languages

TALLY in the Zoo.

Best inclusions:
∀X: TALLYXSPARSEX, cocap.NP/oneX
∀X: NONEXMAJORITYX, NC^0X, PARITYX, TALLYX
Best separations:
∃X: TALLYXAHX, P-SelX, co.SPARSEX
Likeliest blank:
∀X: TALLYX? BPP//logX, BQP/qlogX, CohX, IC[log,poly]X, QMIPX, co.QMIPX
Unlikeliest blank:
∀X: TALLYX? P/logX
Blank case count: 0 ⊆? TALLYX? 16

TC^0: Constant-Depth Threshold Circuits

TC^0 in the Zoo.

Best inclusions:
∀X: ACC^0X, MAC^0XTC^0XNC^1X, TC^0/polyX
Blank case count: 51 ⊆? TC^0X? 15

TC^0/poly: Non-uniform TC^0

Best inclusions: [Bru90]
∀X: AC^0/polyX, PT_1X, TC^0XTC^0/polyXL/polyX
Likeliest blank:
∀X: (k>=5)-PBPX, REGX? TC^0/polyX
Unlikeliest blank:
∀X: TC^0/polyX? IC[log,poly]X
Blank case count: 122 ⊆? TC^0/polyX? 11

TreeBQP: BQP Restricted To Tree States [Aar03b]

TreeBQP in the Zoo.

Best inclusions:
∀X: BPPXTreeBQPXAmpP-BQPX
Likeliest blank:
∀X: TreeBQPX? BPP_{path}X, CohX, FHX, HeurBPPX, MA_EX, MIPX, MIP*X, NE/polyX, NISZK_hX, RG[1]X
Likeliest open: [Aar03b]
∀X: AmpP-BQPX? TreeBQPX? Delta_3PX
Unlikeliest blank:
∀X: NIQSZKX, RQPX, WAPPX? TreeBQPX
Unlikeliest open: [Aar03b]
∀X: AmpP-BQPX? TreeBQPX? Delta_3PX
Blank case count: 36 ⊆? TreeBQPX? 105

UAP: Unambiguous Alternating Polynomial-Time [NR98]

UAP in the Zoo.

Best inclusions: [NR98]
∀X: UPXUAPXSPPX
Likeliest blank:
∀X: cocap.FewPX? UAPX? EHX, NE/polyX, SQGX
Unlikeliest blank:
∀X: EPX, LWPPX? UAPX
Blank case count: 43 ⊆? UAPX? 35

UE: Unambiguous Exponential-Time With Linear Exponent

UE in the Zoo.

Best inclusions:
∀X: UPXUEX+EXPX, NEX
∀X: EXcocap.UEX
Best separations:
∃X: UEXco.MIP_{EXP}X
∃X: cocap.UEXBPEXPX, EXP/polyX
Likeliest blank:
∀X: cocap.FewPX, cocap.HalfPX, cocap.RNCX, cocap.compNPX? UEX
Unlikeliest blank:
∀X: NPX? UEX
∀X: RQPX, YPPX, cocap.NPX? cocap.UEX
Blank case count: 73 ⊆? UEX? 0

UL: Unambiguous L

UL in the Zoo.

Best inclusions:
∀X: ULXFewULX
∀X: LXcocap.ULX
Likeliest blank:
∀X: cocap.FewULX? ULX? co.FewLX
∀X: cocap.ULX? L/polyX, SCX
Unlikeliest blank:
∀X: ULX? cocap.FewULX
∀X: CSLX? cocap.ULX
Blank case count: 82 ⊆? ULX? 60

UP: Unambiguous Polynomial-Time

UP in the Zoo.

Best inclusions:
∀X: UPXFewPX, UAPX, UEX, cocap.RP^{PromiseUP}X, cocap.USX
∀X: PXcocap.UPX
Best separations: [Imp..] [Rub88] [BBB+97]
∃X: FewPXUPXCZKX, Nearly-PX, co.MA_EX, co.NP/polyX, co.QMIPX, co.QMIP_{le}X, co.QMIP_{ne}X
∃X: cocap.UPXAvgEX, BPEX, BQP/qpolyX, CohX, DQPX, HeurBPPX
Likeliest blank:
∀X: cocap.UPX? CZKX, NT*X, Nearly-PX, P-SelX, QSZKX, WAPPX, XOR-MIP*[2,1]X
Unlikeliest blank:
∀X: betaPX? UPX
∀X: NLINSPACEX, QX, cocap.EPX, cocap.betaPX, cocap.compIPX? cocap.UPX
Blank case count: 62 ⊆? UPX? 20

US: Unique Polynomial-Time [BG82]

US in the Zoo.

Best inclusions:
∀X: co.NPXUSXBH_2X
∀X: UPXcocap.USX
Likeliest blank:
∀X: FewPX, HalfPX, NLINX, RNCX, beta_2PX, compNPX? USX
∀X: cocap.USX? A_0PPX, NE/polyX, RP^{PromiseUP}X
Unlikeliest blank:
∀X: USX? C_=PX
∀X: BH_2X, RP^{PromiseUP}X, SPPX, compIPX? cocap.USX? cocap.C_=PX
Blank case count: 87 ⊆? USX? 30

WAPP: Weak Almost-Wide PP [BGM02]

WAPP in the Zoo.

Best inclusions: [BGM02] [BGM02]
∀X: WAPPXAWPPX, SBPX
∀X: BPPXcocap.WAPPX
Best separations: [BGM02]
∃X: WAPPXSigma_2PX
Likeliest blank:
∀X: ZBQPX, cocap.UPX? WAPPX? co.NP/polyX, co.QMIPX, co.QMIP_{le}X, co.QMIP_{ne}X, co.RP^{NP}X
∀X: cocap.WAPPX? (NP-cap-coNP)/polyX, BQP/qpolyX, CZKX, CohX, DQPX, HeurBPPX, MA_EX, N.NISZKX, QMA(2)X, QSZKX, QS_2PX, RG[1]X, XOR-MIP*[2,1]X
Unlikeliest blank:
∀X: N.NISZKX, QMA(2)X, SBPX, frIPX? WAPPX? AC^0/polyX, AVBPPX, AvgEX, BPP/logX, BPQPX, CheckX, FHX, IC[log,poly]X, P-CloseX, QAC^0X, QNC_f^0X, TreeBQPX, ZQPX, co.N.NISZKX, cocap.AM[polylog]X, cocap.CZKX, cocap.NP/oneX, cocap.XOR-MIP*[2,1]X, cocap.compIPX
∀X: CZKX, DQPX, NLINSPACEX, QX, QSZKX, cocap.N.NISZKX, cocap.QMA(2)X, cocap.SBPX, cocap.frIPX? cocap.WAPPX? BPPX, YPPX
Blank case count: 158 ⊆? WAPPX? 226

WPP: Wide PP [FFK94]

WPP in the Zoo.

Best inclusions:
∀X: LWPPXWPPXAWPPX, cocap.C_=PX
Best separations: [STT05] [STT05]
∃X: ZPPXWPPXLWPPX
Unlikeliest blank:
∀X: C_=PX? WPPX
Blank case count: 41 ⊆? WPPX? 34

XOR-MIP*[2,1]: MIP*[2,1] With 1-Bit Proofs [CHT+04]

XOR-MIP*[2,1] in the Zoo.

Best inclusions: [CHT+04]
∀X: XOR-MIP*[2,1]XMIP*X, QMIP_{le}X
∀X: BPPXcocap.XOR-MIP*[2,1]X
Likeliest blank:
∀X: YPX, ZBQPX, cocap.NISZKX, cocap.NLINX, cocap.PZKX, cocap.UPX, cocap.WAPPX, cocap.beta_2PX, cocap.compNPX? XOR-MIP*[2,1]X? co.MIP_{EXP}X, co.NEEX, co.QMIPX
∀X: cocap.XOR-MIP*[2,1]X? +EXPX, BPEEX, CohX, EXP/polyX, NE/polyX, QMIP_{ne}X, QRGX
Unlikeliest blank:
∀X: N.NISZKX, QMIPX, QMIP_{le}X, QMIP_{ne}X? XOR-MIP*[2,1]X? AC^0/polyX, AvgEX, BPPX, IC[log,poly]X, P-CloseX, QAC^0X, QNC_f^0X, YPPX, ZQPX, cocap.C_=PX, cocap.NP/oneX, cocap.compIPX
∀X: CZKX, DQPX, NLINSPACEX, NT*X, QX, WAPPX, cocap.N.NISZKX, cocap.QMIPX, cocap.QMIP_{le}X, cocap.QMIP_{ne}X, frIPX? cocap.XOR-MIP*[2,1]X
Blank case count: 207 ⊆? XOR-MIP*[2,1]X? 386

YP: Your Polynomial-Time or Yaroslav-Percival

YP in the Zoo.

Best inclusions:
∀X: ZPPXYPXYPPX, cocap.NPX
Best separations:
∃X: YPXDQPX
Likeliest blank:
∀X: YPX? APPX, BPEX, BPP//logX, BQP/qlogX, CZKX, CohX, HeurBPPX, QSZKX, XOR-MIP*[2,1]X
Unlikeliest blank:
∀X: QX, YPPX, cocap.betaPX, cocap.compIPX? YPX
Blank case count: 26 ⊆? YPX? 58

YPP: Yaroslav BPP

YPP in the Zoo.

Best inclusions:
∀X: YPXYPPXP/polyX, YQPX, cocap.MAX
Likeliest blank:
∀X: HalfPX, RNCX? YPPX? N.NISZKX, NEX, NP/logX, RP^{PromiseUP}X, SF_4X
Unlikeliest blank:
∀X: AVBPPX, AmpP-BQPX, CZKX, FHX, RBQPX, XOR-MIP*[2,1]X, cocap.WAPPX, cocap.frIPX? YPPX? BPP/logX, CheckX, IC[log,poly]X, YPX, ZPEX, cocap.UEX, cocap.compNPX
Blank case count: 53 ⊆? YPPX? 91

YQP: Yaroslav BQP

YQP in the Zoo.

Best inclusions:
∀X: BQPX, YPPXYQPXBQP/qpolyX, cocap.QMAX
Likeliest blank:
∀X: YQPX? BQP/mpolyX, QCMAX
Unlikeliest blank:
∀X: DQPX, NLINSPACEX, QSZKX, frIPX? YQPX? AVBPPX, AvgEX, BPQPX, BQP/logX, cocap.CZKX, cocap.QCMAX
Blank case count: 48 ⊆? YQPX? 93

ZBQP: Strict Quantum ZPP

ZBQP in the Zoo.

Best inclusions:
∀X: ZBQPXRBQPX
Likeliest blank:
∀X: ZBQPX? AmpP-BQPX, BPEX, CZKX, CohX, FHX, HeurBPPX, P/polyX, WAPPX, XOR-MIP*[2,1]X
Unlikeliest blank:
∀X: ZBQPX? cocap.RNCX, cocap.compNPX
Blank case count: 14 ⊆? ZBQPX? 77

ZPE: Zero-Error Probabilistic E

ZPE in the Zoo.

Best inclusions:
∀X: EXZPEXRPEX
Best separations:
∃X: ZPEX+EXPX, EXP/polyX
Unlikeliest blank:
∀X: RQPX, YPPX? ZPEX
Blank case count: 29 ⊆? ZPEX? 1

ZPP: Zero-Error Probabilistic Polynomial-Time

ZPP in the Zoo.

Best inclusions:
∀X: ZPPXRPX, YPX
Best separations: [BBF98] [BBF98] [STT05]
∃X: ZPPX+PX, EX, Mod_3PX, Mod_5PX, P/logX, WPPX
Blank case count: 15 ⊆? ZPPX? 32

ZPP^{NP}: ZPP With NP Oracle

Best inclusions: [Cai01]
∀X: S_2PX, cocap.AMXZPP^{NP}XRP^{NP}X
Unlikeliest blank:
∀X: cocap.Sigma_2PX? ZPP^{NP}X
Blank case count: 74 ⊆? ZPP^{NP}X? 14

ZQP: Zero-Error Extension of EQP [BW03] [Nis02]

ZQP in the Zoo.

Best inclusions:
∀X: EQPXZQPXRQPX
Unlikeliest blank:
∀X: AVBPPX, CheckX, NIQSZKX, PZKX, WAPPX, XOR-MIP*[2,1]X, cocap.NISZK_hX? ZQPX
Blank case count: 41 ⊆? ZQPX? 112

Last modified: Thu, 17 Aug 2006
Greg Kuperberg