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:

• Complexity Zoology Introduction
• Active Inclusion Diagram
• Static Inclusion Diagram

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-PBP^X, MAJORITY^X ⊆ (k>=5)-PBP^X ⊆ NC^1^X, PBP^X

Best separations:

∃X: (k>=5)-PBP^X ⊈ PL_{infty}^X

Likeliest blank:

∀X: (k>=5)-PBP^X ⊆^? TC^0/poly^X

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

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

Best inclusions:

∀X: P/poly^X, cocap.NP^X ⊆ (NP-cap-coNP)/poly^X ⊆ cocap.NP/poly^X

Best separations: [FFK+93]

∃X: cocap.NP/one^X ⊈ (NP-cap-coNP)/poly^X

Likeliest blank:

∀X: PZK^X, cocap.N.BPP^X, cocap.NISZK^X, cocap.WAPP^X ⊆^? (NP-cap-coNP)/poly^X

Likeliest open:

∀X: cocap.PZK^X ⊆^? (NP-cap-coNP)/poly^X

Unlikeliest blank:

∀X: BQP/qpoly^X, DQP^X, cocap.N.NISZK^X, cocap.QMIP^X, cocap.QMIP_{le}^X, cocap.QMIP_{ne}^X ⊆^? (NP-cap-coNP)/poly^X

Unlikeliest open:

∀X: cocap.PZK^X ⊆^? (NP-cap-coNP)/poly^X

+EXP: Parity EXP

+EXP in the Zoo.

Best inclusions:

∀X: EXP^X, UE^X ⊆ +EXP^X ⊆ EXPSPACE^X

Best separations: [BBF98]

∃X: BPQP^X, ZPE^X ⊈ +EXP^X ⊈ BPEE^X, NEE^X, NEXP/poly^X, SEH^X

Likeliest blank:

∀X: Almost-PSPACE^X, Check^X, QRG^X, cocap.QMA(2)^X, cocap.XOR-MIP*[2,1]^X ⊆^? +EXP^X ⊆^? EXPH^X, PEXP^X

Unlikeliest blank:

∀X: +EXP^X ⊆^? EXP^{NP}^X, PEXP^X

+L: Parity L

+L in the Zoo.

Best inclusions: [GW96] [CKS81]

∀X: SPL^X ⊆ +L^X ⊆ +L/poly^X, +SAC^1^X, AL^X

Likeliest blank:

∀X: cocap.R_HL^X ⊆^? +L^X ⊆^? AC^1^X, L^{DET}^X

+L/poly: Nonuniform +L

+L/poly in the Zoo.

Best inclusions: [GW96]

∀X: +L^X, NL/poly^X ⊆ +L/poly^X ⊆ P/poly^X

Likeliest blank:

∀X: DCFL^X, FOLL^X, cocap.C_=L^X ⊆^? +L/poly^X

+P: Parity P

+P in the Zoo.

Best inclusions: [GHJ+91]

∀X: NT*^X, SPP^X ⊆ +P^X ⊆ ModP^X, SF_2^X

Best separations:

∃X: Mod_3P^X, Mod_5P^X, ZPP^X, compNP^X ⊈ +P^X

Likeliest blank:

∀X: cocap.HalfP^X ⊆^? +P^X

Unlikeliest blank:

∀X: +P^X ⊆^? NT*^X

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

+SAC^0 in the Zoo.

Best inclusions: [Moo99]

∀X: NC^0^X, PARITY^X ⊆ +SAC^0^X ⊆ AC^0[2]^X, QNC_f^0^X

Best separations:

∃X: +SAC^0^X ⊈ CSL^X, PL_{infty}^X, QCFL^X

Unlikeliest blank:

∀X: AC^0[2]^X, LIN^X, QAC^0^X, QNC_f^0^X ⊆^? +SAC^0^X

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

+SAC^1 in the Zoo.

Best inclusions: [GW96] [GW96]

∀X: +L^X, SAC^1^X ⊆ +SAC^1^X ⊆ NC^2^X

Likeliest blank:

∀X: BPL^X, FOLL^X, cocap.C_=L^X ⊆^? +SAC^1^X

Unlikeliest blank:

∀X: +SAC^1^X ⊆^? ACC^0^X, cocap.1NAuxPDA^p^X

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

1NAuxPDA^p in the Zoo.

Best inclusions: [Bra77] [Bra77]

∀X: CFL^X ⊆ 1NAuxPDA^p^X ⊆ SAC^1^X

Likeliest blank:

∀X: 2-PBP^X, NC^0^X, co.CFL^X, cocap.GCSL^X ⊆^? 1NAuxPDA^p^X

∀X: cocap.1NAuxPDA^p^X ⊆^? CSL^X, Q^X, QCFL^X

Unlikeliest blank:

∀X: 1NAuxPDA^p^X ⊆^? 3-PBP^X, LIN^X, cocap.CFL^X

∀X: +SAC^1^X, AC^1^X, AL^X, LIN^X, QCFL^X, QNC^1^X, SC^X ⊆^? cocap.1NAuxPDA^p^X ⊆^? DCFL^X

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

Best inclusions:

∀X: PARITY^X ⊆ 2-PBP^X ⊆ 3-PBP^X, AC^0[2]^X

Best separations:

∃X: NC^0^X, REG^X ⊈ 2-PBP^X

Likeliest blank:

∀X: 2-PBP^X ⊆^? 1NAuxPDA^p^X, PL_{infty}^X, Q^X, QCFL^X, QNC_f^0^X

Unlikeliest blank:

∀X: 2-PBP^X ⊆^? PARITY^X

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

Best inclusions:

∀X: 2-PBP^X ⊆ 3-PBP^X ⊆ 4-PBP^X

Best separations:

∃X: 3-PBP^X ⊈ AC^0[2]^X

Likeliest open:

∀X: 4-PBP^X ⊆^? 3-PBP^X

Unlikeliest blank:

∀X: 1NAuxPDA^p^X, GCSL^X, PBP^X, QCFL^X, QNC^0^X, cocap.SAC^0^X ⊆^? 3-PBP^X

Unlikeliest open:

∀X: 4-PBP^X ⊆^? 3-PBP^X

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

Best inclusions: [BT88]

∀X: 3-PBP^X ⊆ 4-PBP^X ⊆ (k>=5)-PBP^X, ACC^0^X

Likeliest open:

∀X: 4-PBP^X ⊆^? 3-PBP^X

Unlikeliest blank:

∀X: 4-PBP^X ⊆^? PL_1^X, REG^X

Unlikeliest open:

∀X: 4-PBP^X ⊆^? 3-PBP^X

A_0PP: One-Sided Analog of AWPP [Vya03]

A_0PP in the Zoo.

Best inclusions: [Vya03] [Vya03]

∀X: QMA^X, co.C_=P^X ⊆ A_0PP^X ⊆ PP^X

∀X: AWPP^X, EP^X ⊆ cocap.A_0PP^X

Likeliest blank:

∀X: APP^X, C_=P^X, co.NLIN^X, co.beta_2P^X, co.compNP^X, cocap.SBP^X, cocap.US^X ⊆^? A_0PP^X

Unlikeliest blank:

∀X: A_0PP^X ⊆^? BPP_{path}^X, co.C_=P^X, cocap.RP^{PromiseUP}^X

∀X: cocap.A_0PP^X ⊆^? cocap.C_=P^X

AC^0: Unbounded Fanin Constant-Depth Circuits

AC^0 in the Zoo.

Best inclusions:

∀X: SAC^0^X ⊆ AC^0^X ⊆ AC^0/poly^X, AC^0[2]^X, FOLL^X, MAC^0^X, QAC^0^X

Best separations: [BS90] [BKL+00]

∃X: FOLL^X ⊈ AC^0^X ⊈ PL_{infty}^X

Unlikeliest blank:

∀X: QAC^0^X ⊆^? AC^0^X

AC^0/poly: Nonuniform AC^0

Best inclusions:

∀X: AC^0^X, SPARSE^X ⊆ AC^0/poly^X ⊆ TC^0/poly^X

Likeliest blank:

∀X: FOLL^X, MAJORITY^X, PARITY^X ⊆^? AC^0/poly^X ⊆^? Nearly-P^X

Unlikeliest blank:

∀X: AVBPP^X, AmpP-BQP^X, CSL^X, CZK^X, FH^X, P-Sel^X, P/poly^X, Q^X, QCFL^X, QNC^X, RBQP^X, WAPP^X, XOR-MIP*[2,1]^X, cocap.betaP^X, cocap.frIP^X ⊆^? AC^0/poly^X

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

Best inclusions:

∀X: +SAC^0^X, 2-PBP^X, AC^0^X ⊆ AC^0[2]^X ⊆ ACC^0^X

Best separations: [Raz87]

∃X: 3-PBP^X, MAJORITY^X ⊈ AC^0[2]^X

Unlikeliest blank:

∀X: AC^0[2]^X ⊆^? +SAC^0^X

AC^1: Unbounded Fanin Log-Depth Circuits

AC^1 in the Zoo.

Best inclusions:

∀X: FOLL^X, SAC^1^X ⊆ AC^1^X ⊆ NC^2^X

Best separations: [Mil92]

∃X: NC^2^X ⊈ AC^1^X ⊈ NC^1^X

Likeliest blank:

∀X: +L^X, BPL^X, cocap.C_=L^X ⊆^? AC^1^X

Likeliest open:

∀X: SPL^X ⊆^? AC^1^X

Unlikeliest blank:

∀X: AC^1^X ⊆^? L^X, cocap.1NAuxPDA^p^X

Unlikeliest open:

∀X: SPL^X ⊆^? AC^1^X

ACC^0: AC^0 With Arbitrary MOD Gates

ACC^0 in the Zoo.

Best inclusions: [BT88]

∀X: 4-PBP^X, AC^0[2]^X ⊆ ACC^0^X ⊆ QACC^0^X, TC^0^X

Unlikeliest blank:

∀X: +SAC^1^X, AL^X, QNC^1^X, SC^X ⊆^? ACC^0^X

AH: Arithmetic Hierarchy

AH in the Zoo.

Best inclusions:

∀X: RE^X ⊆ AH^X ⊆ ALL^X

Best separations:

∃X: Coh^X, P-Sel^X, P/log^X, TALLY^X ⊈ AH^X

Likeliest blank:

∀X: cocap.MIP*^X ⊆^? AH^X

AL: Alternating L

AL in the Zoo.

Best inclusions: [CKS81] [CKS81] [CKS81]

∀X: +L^X, L^{DET}^X ⊆ AL^X ⊆ P^X

Likeliest blank:

∀X: DCFL^X, FOLL^X ⊆^? AL^X ⊆^? NLINSPACE^X, QNC^X

Unlikeliest blank:

∀X: HalfP^X, QNC^X ⊆^? AL^X ⊆^? ACC^0^X, cocap.1NAuxPDA^p^X

ALL: The Class of All Languages

ALL in the Zoo.

Best inclusions:

∀X: AH^X, Coh^X, NEXP/poly^X, Nearly-P^X, P-Sel^X, PL_{infty}^X, QMIP^X ⊆ ALL^X

Almost-PSPACE: Languages Almost Surely in PSPACE^A

Almost-PSPACE in the Zoo.

Best inclusions:

∀X: PSPACE^X ⊆ Almost-PSPACE^X ⊆ BPEXP^X

Best separations:

∃X: AvgP^X, QPLIN^X ⊈ Almost-PSPACE^X

Likeliest blank:

∀X: AVBPP^X, QS_2P^X, RG^X, cocap.QIP[2]^X ⊆^? Almost-PSPACE^X ⊆^? +EXP^X, EXP^{NP}^X, NEE^X, NEXP/poly^X, SEH^X

Likeliest open:

∀X: DQP^X ⊆^? Almost-PSPACE^X

Unlikeliest blank:

∀X: Almost-PSPACE^X ⊆^? BP.PP^X, EH^X, ModP^X, P-Sel^X, P^{QMA}^X, RG[1]^X, SF_2^X

Unlikeliest open:

∀X: DQP^X ⊆^? Almost-PSPACE^X

AM: Arthur-Merlin [BM88]

AM in the Zoo.

Best inclusions: [BM88] [BM88] [BGM02]

∀X: SBP^X ⊆ AM^X ⊆ AM[polylog]^X, BPP^{NP}^X, NP/poly^X, QAM^X, co.Sigma_2P^X

∀X: SZK^X ⊆ cocap.AM^X ⊆ ZPP^{NP}^X

Best separations: [AGH90] [Ver92]

∃X: AM[polylog]^X ⊈ AM^X

∃X: cocap.AM^X ⊈ PP^X

Unlikeliest blank:

∀X: QIP[2]^X ⊆^? AM^X

∀X: cocap.QMIP^X, cocap.QMIP_{le}^X, cocap.QMIP_{ne}^X ⊆^? cocap.AM^X

AM[polylog]: AM With Polylog Rounds

AM[polylog] in the Zoo.

Best inclusions:

∀X: AM^X ⊆ AM[polylog]^X ⊆ IP^X

Best separations: [AGH90] [AGH90]

∃X: IP^X ⊈ AM[polylog]^X ⊈ AM^X

Likeliest blank:

∀X: cocap.CZK^X, cocap.compIP^X ⊆^? AM[polylog]^X

∀X: cocap.AM[polylog]^X ⊆^? CH^X, EH^X, NE/poly^X, PP/poly^X, QIP[2]^X

Unlikeliest blank:

∀X: NT*^X, WAPP^X, frIP^X ⊆^? cocap.AM[polylog]^X

AM_{EXP}: Exponential-Time AM

AM_{EXP} in the Zoo.

Best inclusions:

∀X: MA_{EXP}^X ⊆ AM_{EXP}^X ⊆ IP_{EXP}^X, co.NEXP^{NP}^X

Best separations: [Ver92]

∃X: cocap.AM_{EXP}^X ⊈ PEXP^X

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

AmpMP: Amplifiable MP [GKR+95]

AmpMP in the Zoo.

Best inclusions: [KT96]

∀X: ModP^X ⊆ AmpMP^X ⊆ MP^X

Likeliest blank:

∀X: cocap.NLIN^X, cocap.RNC^X, cocap.beta_2P^X, cocap.compNP^X ⊆^? AmpMP^X ⊆^? ModP^X

AmpP-BQP: BQP Restricted To AmpP States

AmpP-BQP in the Zoo.

Best inclusions:

∀X: TreeBQP^X ⊆ AmpP-BQP^X ⊆ BQP^X, cocap.Sigma_3P^X

Likeliest blank:

∀X: ZBQP^X ⊆^? AmpP-BQP^X

Likeliest open:

∀X: AmpP-BQP^X ⊆^? TreeBQP^X

Unlikeliest blank:

∀X: AmpP-BQP^X ⊆^? AC^0/poly^X, BPP^X, IC[log,poly]^X, P-Close^X, YPP^X, cocap.compIP^X

Unlikeliest open:

∀X: AmpP-BQP^X ⊆^? TreeBQP^X

APP: Amplified PP [Li93]

APP in the Zoo.

Best inclusions: [Fen02]

∀X: AWPP^X ⊆ APP^X ⊆ PP^X

Likeliest blank:

∀X: YP^X, cocap.EP^X, cocap.NLIN^X, cocap.beta_2P^X, cocap.compNP^X ⊆^? APP^X ⊆^? A_0PP^X

Unlikeliest blank:

∀X: APP^X ⊆^? BPP_{path}^X, cocap.C_=P^X, cocap.RP^{PromiseUP}^X

AVBPP: Average-Case BPP [OW93]

AVBPP in the Zoo.

Best inclusions:

∀X: BPP^X ⊆ AVBPP^X ⊆ HeurBPP^X

Best separations:

∃X: AvgP^X ⊈ AVBPP^X

Likeliest blank:

∀X: AVBPP^X ⊆^? Almost-PSPACE^X, Coh^X, DQP^X, ESPACE^X, NE/poly^X, PP/poly^X, QMIP^X, QMIP_{le}^X, QMIP_{ne}^X, QRG^X

Unlikeliest blank:

∀X: CZK^X, DQP^X, NLINSPACE^X, NT*^X, Q^X, QSZK^X, SUBEXP^X, WAPP^X, YQP^X, frIP^X ⊆^? AVBPP^X ⊆^? AC^0/poly^X, BPP^X, IC[log,poly]^X, ModP^X, P-Close^X, P-Sel^X, QAC^0^X, QNC_f^0^X, SF_2^X, YPP^X, ZQP^X, cocap.C_=P^X, cocap.NP/one^X, cocap.RP^{PromiseUP}^X, cocap.compIP^X

AvgE: Average Exponential-Time With Linear Exponent

AvgE in the Zoo.

Best inclusions:

∀X: E^X ⊆ AvgE^X ⊆ EE^X

Best separations:

∃X: cocap.UP^X ⊈ AvgE^X ⊈ EXPSPACE^X, MIP_{EXP}^X, NEXP/poly^X

Likeliest blank:

∀X: NT*^X, QAC^0^X, QCFL^X, QNC^0^X, cocap.HalfP^X, cocap.RNC^X, cocap.compNP^X ⊆^? AvgE^X

Unlikeliest blank:

∀X: BPE^X, CZK^X, DQP^X, HeurBPP^X, QSZK^X, WAPP^X, XOR-MIP*[2,1]^X, YQP^X, frIP^X ⊆^? AvgE^X

AvgP: Average Polynomial-Time [Lev86]

AvgP in the Zoo.

Best inclusions:

∀X: P^X ⊆ AvgP^X ⊆ E^X, HeurBPP^X, Nearly-P^X

Best separations:

∃X: AvgP^X ⊈ AVBPP^X, Almost-PSPACE^X, DQP^X, P-Sel^X, PP/poly^X, QMIP^X, QMIP_{le}^X, QMIP_{ne}^X, QPSPACE^X, QRG^X, SUBEXP^X

Likeliest blank:

∀X: AvgP^X ⊆^? Coh^X

Unlikeliest blank:

∀X: EQP^X, NT*^X, compIP^X, polyL^X ⊆^? AvgP^X

AWPP: Almost WPP [FFK94]

AWPP in the Zoo.

Best inclusions: [Fen02] [FR98] [BGM02]

∀X: BQP^X, WAPP^X, WPP^X ⊆ AWPP^X ⊆ APP^X, cocap.A_0PP^X

Unlikeliest blank:

∀X: PP^X, P^{NP[log^2]}^X, RP^{PromiseUP}^X ⊆^? AWPP^X

beta_2P: Log-Squared Nondeterminism NP [KF84]

Best inclusions:

∀X: beta_2P^X ⊆ QPLIN^X, betaP^X

∀X: P^X ⊆ cocap.beta_2P^X

Best separations: [Imp..]

∃X: beta_2P^X ⊈ co.NP/poly^X, co.QMIP^X, co.QMIP_{le}^X, co.QMIP_{ne}^X

∃X: cocap.beta_2P^X ⊈ CZK^X, Coh^X, DQP^X, Nearly-P^X

Likeliest blank:

∀X: beta_2P^X ⊆^? US^X, co.A_0PP^X, co.RP^{PromiseUP}^X

∀X: cocap.beta_2P^X ⊆^? APP^X, AmpMP^X, BQP/qpoly^X, C_=P^X, HeurBPP^X, P-Sel^X, QSZK^X, XOR-MIP*[2,1]^X

Unlikeliest blank:

∀X: NLINSPACE^X, Q^X, cocap.compIP^X ⊆^? cocap.beta_2P^X

betaP: Limited-Nondeterminism NP [KF84]

betaP in the Zoo.

Best inclusions:

∀X: beta_2P^X ⊆ betaP^X ⊆ NP^X, QP^X

Best separations:

∃X: cocap.betaP^X ⊈ QPLIN^X

Unlikeliest blank:

∀X: betaP^X ⊆^? BQP/log^X, NLIN^X, NT^X, UP^X, polyL^X

∀X: cocap.betaP^X ⊆^? AC^0/poly^X, P/log^X, YP^X, cocap.NLIN^X, cocap.UP^X

BH: Boolean Hierarchy Over NP [WW85]

BH in the Zoo.

Best inclusions:

∀X: BH_2^X ⊆ BH^X ⊆ P^{NP[log]}^X

Best separations:

∃X: P^{NP[log]}^X ⊈ BH^X ⊈ BH_2^X

BH_2: Second Level of Boolean Hierarchy

Best inclusions:

∀X: US^X ⊆ BH_2^X ⊆ BH^X

Best separations:

∃X: BH^X ⊈ BH_2^X

Unlikeliest blank:

∀X: BH_2^X ⊆^? cocap.US^X

BP.PP: PP with BP operator

Best inclusions: [MW05]

∀X: PH^X, PP^X, QAM^X ⊆ BP.PP^X ⊆ CH^X, PP/poly^X

Unlikeliest blank:

∀X: Almost-PSPACE^X, QRG^X ⊆^? BP.PP^X

BPE: Bounded-Error Probabilistic E

BPE in the Zoo.

Best inclusions:

∀X: BPQP^X, RPE^X ⊆ BPE^X ⊆ BPEXP^X, cocap.MA_E^X

Best separations:

∃X: cocap.UP^X ⊈ BPE^X ⊈ SEH^X

Likeliest blank:

∀X: YP^X, ZBQP^X, cocap.compNP^X ⊆^? BPE^X

Unlikeliest blank:

∀X: HeurBPP^X ⊆^? BPE^X ⊆^? AvgE^X

BPEE: Bounded-Error Probabilistic EE

BPEE in the Zoo.

Best inclusions:

∀X: BPEXP^X, EE^X ⊆ BPEE^X ⊆ EESPACE^X

Best separations:

∃X: +EXP^X, cocap.NEXP^X ⊈ BPEE^X ⊈ NEEXP^X

Likeliest blank:

∀X: Check^X, QRG^X, cocap.QMA(2)^X, cocap.XOR-MIP*[2,1]^X ⊆^? BPEE^X

BPEXP: Bounded-Error Probabilistic EXP

Best inclusions:

∀X: Almost-PSPACE^X, BPE^X, EXP^X ⊆ BPEXP^X ⊆ BPEE^X, cocap.MA_{EXP}^X

Best separations:

∃X: cocap.UE^X ⊈ BPEXP^X ⊈ NEE^X

BPL: Bounded-Error Probabilistic L

BPL in the Zoo.

Best inclusions: [Nis92]

∀X: RL^X ⊆ BPL^X ⊆ L/poly^X, PL^X, SC^X

Likeliest blank:

∀X: BPL^X ⊆^? +SAC^1^X, AC^1^X, C_=L^X

Unlikeliest blank:

∀X: NC^2^X ⊆^? BPL^X

BPP: Bounded-Error Probabilistic Polynomial-Time

BPP in the Zoo.

Best inclusions:

∀X: RP^X ⊆ BPP^X ⊆ AVBPP^X, BPP/log^X, BPQP^X, Check^X, FH^X, TreeBQP^X, cocap.N.BPP^X, cocap.NISZK^X, cocap.PZK^X, cocap.WAPP^X, cocap.XOR-MIP*[2,1]^X

Best separations:

∃X: BPP^X ⊈ Delta_2P^X, NE^X

Likeliest blank:

∀X: BPP^X ⊆^? SF_4^X

Unlikeliest blank:

∀X: AVBPP^X, AmpP-BQP^X, Check^X, FH^X, NISZK^X, PZK^X, XOR-MIP*[2,1]^X, cocap.NISZK_h^X, cocap.WAPP^X ⊆^? BPP^X

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

BPP//log in the Zoo.

Best inclusions:

∀X: BPP/rlog^X ⊆ BPP//log^X ⊆ P/poly^X

Best separations:

∃X: SPARSE^X ⊈ BPP//log^X

Likeliest blank:

∀X: IC[log,poly]^X, TALLY^X, YP^X ⊆^? BPP//log^X ⊆^? BQP/qlog^X

Unlikeliest blank:

∀X: BPP//log^X ⊆^? BPP/log^X, IC[log,poly]^X, cocap.NP/one^X

BPP/log: BPP With Logarithmic Karp-Lipton Advice

BPP/log in the Zoo.

Best inclusions:

∀X: BPP^X, P/log^X ⊆ BPP/log^X ⊆ BPP/mlog^X, BQP/log^X

Unlikeliest blank:

∀X: BPP//log^X, CZK^X, WAPP^X, YPP^X, cocap.frIP^X ⊆^? BPP/log^X

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

BPP/mlog in the Zoo.

Best inclusions:

∀X: BPP/log^X ⊆ BPP/mlog^X ⊆ BPP/rlog^X, BQP/mlog^X

Likeliest blank:

∀X: BPP/mlog^X ⊆^? BQP/log^X

Unlikeliest blank:

∀X: IC[log,poly]^X, P-Sel^X ⊆^? BPP/mlog^X

BPP/rlog: BPP With Logarithmic Randomized Advice

BPP/rlog in the Zoo.

Best inclusions:

∀X: BPP/mlog^X ⊆ BPP/rlog^X ⊆ BPP//log^X, BQP/qlog^X

Likeliest blank:

∀X: BPP/rlog^X ⊆^? BQP/mlog^X

BPP^{NP}: BPP With NP Oracle

Best inclusions: [HHT97]

∀X: AM^X, BPP_{path}^X, RP^{NP}^X ⊆ BPP^{NP}^X ⊆ Delta_3P^X, SQG^X

Likeliest blank:

∀X: cocap.N.NISZK^X ⊆^? BPP^{NP}^X

Unlikeliest blank:

∀X: Delta_3P^X, SQG^X ⊆^? BPP^{NP}^X

BPP_{path}: Threshold BPP [HHT97]

BPP_{path} in the Zoo.

Best inclusions: [HHT97] [HHT97] [HHT97] [BGM02]

∀X: P^{NP[log]}^X, SBP^X ⊆ BPP_{path}^X ⊆ BPP^{NP}^X, PP^X

Likeliest blank:

∀X: Few^X, TreeBQP^X ⊆^? BPP_{path}^X

Unlikeliest blank:

∀X: APP^X, A_0PP^X, P^{NP[log^2]}^X ⊆^? BPP_{path}^X

BPQP: Bounded-Error Probabilistic QP [CNS99]

BPQP in the Zoo.

Best inclusions:

∀X: BPP^X, QP^X ⊆ BPQP^X ⊆ BPE^X, QPSPACE^X

Best separations: [BBF98] [Hel86]

∃X: BPQP^X ⊈ +EXP^X, EXP^{NP}^X

Likeliest blank:

∀X: NT^X, cocap.CSL^X, cocap.NLIN^X ⊆^? BPQP^X ⊆^? NEXP/poly^X, SEH^X

Unlikeliest blank:

∀X: CZK^X, DQP^X, NT*^X, QSZK^X, WAPP^X, YQP^X, frIP^X ⊆^? BPQP^X ⊆^? BQP/mpoly^X, SEH^X

BQP: Bounded-Error Quantum Polynomial-Time

BQP in the Zoo.

Best inclusions: [FR98] [Aar02b]

∀X: AmpP-BQP^X, FH^X, QCFL^X, QNC^X, RQP^X ⊆ BQP^X ⊆ AWPP^X, BQP/log^X, DQP^X, YQP^X, cocap.NIQSZK^X, cocap.QCMA^X

Best separations: [Aar02]

∃X: NISZK_h^X ⊈ BQP^X ⊈ MA^X

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

BQP/log in the Zoo.

Best inclusions:

∀X: BPP/log^X, BQP^X ⊆ BQP/log^X ⊆ BQP/mlog^X

Best separations:

∃X: IC[log,poly]^X, P-Sel^X, QPLIN^X ⊈ BQP/log^X

Likeliest blank:

∀X: BPP/mlog^X ⊆^? BQP/log^X

Unlikeliest blank:

∀X: BQP/mlog^X, DQP^X, QSZK^X, YQP^X, betaP^X ⊆^? BQP/log^X

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

BQP/mlog in the Zoo.

Best inclusions:

∀X: BPP/mlog^X, BQP/log^X ⊆ BQP/mlog^X ⊆ BQP/qlog^X

Best separations: [NY03]

∃X: BQP/qlog^X ⊈ BQP/mlog^X

Likeliest blank:

∀X: BPP/rlog^X ⊆^? BQP/mlog^X

Unlikeliest blank:

∀X: QPLIN^X ⊆^? BQP/mlog^X ⊆^? BQP/log^X, cocap.NP/one^X

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

BQP/mpoly in the Zoo.

Best inclusions:

∀X: BQP/poly^X ⊆ BQP/mpoly^X ⊆ BQP/qpoly^X

Likeliest blank:

∀X: YQP^X ⊆^? BQP/mpoly^X ⊆^? BQP/poly^X

Unlikeliest blank:

∀X: BPQP^X, NLINSPACE^X, NT*^X, SUBEXP^X, frIP^X ⊆^? BQP/mpoly^X

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

BQP/poly in the Zoo.

Best inclusions: [NY03]

∀X: BQP/qlog^X, P/poly^X ⊆ BQP/poly^X ⊆ BQP/mpoly^X

Best separations:

∃X: NT^X, compNP^X, polyL^X ⊈ BQP/poly^X

Likeliest blank:

∀X: BQP/mpoly^X ⊆^? BQP/poly^X

Unlikeliest blank:

∀X: BQP/qpoly^X ⊆^? BQP/poly^X

BQP/qlog: BQP With Logarithmic-Size Quantum Advice

BQP/qlog in the Zoo.

Best inclusions: [NY03]

∀X: BPP/rlog^X, BQP/mlog^X ⊆ BQP/qlog^X ⊆ BQP/poly^X

Best separations: [NY03]

∃X: SPARSE^X ⊈ BQP/qlog^X ⊈ BQP/mlog^X, NP/log^X

Likeliest blank:

∀X: BPP//log^X, IC[log,poly]^X, TALLY^X, YP^X ⊆^? BQP/qlog^X

BQP/qpoly: BQP With Polynomial-Size Quantum Advice

BQP/qpoly in the Zoo.

Best inclusions: [Aar04b]

∀X: BQP/mpoly^X, YQP^X ⊆ BQP/qpoly^X ⊆ PP/poly^X

Best separations: [BBB+97]

∃X: cocap.UP^X ⊈ BQP/qpoly^X

Likeliest blank:

∀X: cocap.NISZK^X, cocap.NLIN^X, cocap.PZK^X, cocap.WAPP^X, cocap.beta_2P^X, cocap.compNP^X ⊆^? BQP/qpoly^X

Unlikeliest blank:

∀X: BQP/qpoly^X ⊆^? (NP-cap-coNP)/poly^X, BQP/poly^X, Nearly-P^X, cocap.MIP*^X

C_=L: Exact-Counting L

C_=L in the Zoo.

Best inclusions:

∀X: C_=L^X ⊆ PL^X

∀X: NL^X, SPL^X ⊆ cocap.C_=L^X

Likeliest blank:

∀X: BPL^X ⊆^? C_=L^X ⊆^? co.C_=L^X

∀X: cocap.C_=L^X ⊆^? +L/poly^X, +SAC^1^X, AC^1^X

C_=P: Exact-Counting Polynomial-Time

C_=P in the Zoo.

Best inclusions: [Vya03] [BHR00]

∀X: EP^X ⊆ C_=P^X ⊆ co.A_0PP^X

∀X: WPP^X ⊆ cocap.C_=P^X

Best separations:

∃X: NP^X ⊈ C_=P^X

Likeliest blank:

∀X: QAC^0^X, QCFL^X, QNC^0^X, co.EP^X, cocap.NLIN^X, cocap.RNC^X, cocap.beta_2P^X, cocap.compNP^X ⊆^? C_=P^X ⊆^? A_0PP^X

Unlikeliest blank:

∀X: US^X, co.A_0PP^X, co.N.NISZK^X, co.QMA(2)^X, co.RP^{PromiseUP}^X, co.SBP^X ⊆^? C_=P^X ⊆^? Mod_3P^X, Mod_5P^X, NT*^X, S_2P^X, WPP^X

∀X: APP^X, AVBPP^X, CZK^X, DQP^X, QSZK^X, XOR-MIP*[2,1]^X, cocap.A_0PP^X, cocap.N.NISZK^X, cocap.QMA(2)^X, cocap.RP^{PromiseUP}^X, cocap.SBP^X, cocap.US^X, frIP^X ⊆^? cocap.C_=P^X

CFL: Context-Free Languages

CFL in the Zoo.

Best inclusions: [Bra77]

∀X: CFL^X ⊆ 1NAuxPDA^p^X, GCSL^X, NLIN^X, QCFL^X

∀X: DCFL^X, MAJORITY^X ⊆ cocap.CFL^X

Best separations: [GG66] [MC00]

∃X: QCFL^X ⊈ CFL^X ⊈ DCFL^X

Likeliest blank:

∀X: CFL^X ⊆^? co.1NAuxPDA^p^X, co.CSL^X, co.Q^X

∀X: cocap.CFL^X ⊆^? SC^X

Unlikeliest blank:

∀X: 1NAuxPDA^p^X, CSL^X ⊆^? cocap.CFL^X

CH: Counting Hierarchy [Wag86]

CH in the Zoo.

Best inclusions: [Ogi94] [Her97]

∀X: BP.PP^X, MP^{#P}^X, SF_4^X ⊆ CH^X ⊆ PSPACE^X

Likeliest blank:

∀X: RG[1]^X, cocap.AM[polylog]^X, cocap.CSL^X, cocap.CZK^X, cocap.NIQSZK^X, cocap.compIP^X, polyL^X ⊆^? CH^X

Check: Checkable Languages [BK89]

Check in the Zoo.

Best inclusions:

∀X: BPP^X ⊆ Check^X ⊆ cocap.frIP^X

Likeliest blank:

∀X: cocap.compNP^X ⊆^? Check^X ⊆^? +EXP^X, BPEE^X, EXP/poly^X, NE/poly^X, QMA(2)^X, QMIP^X, QMIP_{le}^X, QRG^X

Unlikeliest blank:

∀X: CZK^X, NT*^X, Q^X, WAPP^X, YPP^X, frIP^X ⊆^? Check^X ⊆^? BPP^X, QAC^0^X, QNC_f^0^X, ZQP^X

Coh: Coherent Languages [Yao90b]

Coh in the Zoo.

Best inclusions: [Yao90b]

∀X: frIP^X ⊆ Coh^X ⊆ ALL^X

Best separations:

∃X: EQP^X, cocap.UP^X, cocap.beta_2P^X, polyL^X ⊈ Coh^X ⊈ AH^X, NEXP/poly^X, Nearly-P^X

Likeliest blank:

∀X: AVBPP^X, AvgP^X, FH^X, NT^X, P-Sel^X, P/log^X, QAC^0^X, QCFL^X, QNC^0^X, TALLY^X, TreeBQP^X, YP^X, ZBQP^X, cocap.CSL^X, cocap.NISZK^X, cocap.NLIN^X, cocap.PZK^X, cocap.WAPP^X, cocap.XOR-MIP*[2,1]^X ⊆^? Coh^X

Unlikeliest blank:

∀X: HeurBPP^X, Nearly-P^X, P-Sel^X, P/poly^X, PL_{infty}^X ⊆^? Coh^X ⊆^? P-Sel^X, cocap.MIP*^X

compIP: Competitive IP Proof System

compIP in the Zoo.

Best inclusions: [BG94]

∀X: compNP^X ⊆ compIP^X ⊆ IP^X, frIP^X

Likeliest blank:

∀X: cocap.HalfP^X, cocap.RNC^X ⊆^? compIP^X

∀X: cocap.compIP^X ⊆^? AM[polylog]^X, CH^X, EH^X, NE/poly^X, PP/poly^X, QIP[2]^X, QMA(2)^X, QS_2P^X, RG[1]^X

Unlikeliest blank:

∀X: compIP^X ⊆^? AvgP^X, LWPP^X, NLIN^X, cocap.US^X, compNP^X

∀X: AVBPP^X, AmpP-BQP^X, CZK^X, FH^X, NT*^X, RBQP^X, WAPP^X, XOR-MIP*[2,1]^X, frIP^X ⊆^? cocap.compIP^X ⊆^? NT^X, P/log^X, YP^X, cocap.NLIN^X, cocap.UP^X, cocap.beta_2P^X, cocap.compNP^X, polyL^X

compNP: Competitive NP Proof System

compNP in the Zoo.

Best inclusions:

∀X: compNP^X ⊆ NP^X, compIP^X

∀X: P^X ⊆ cocap.compNP^X

Best separations:

∃X: compNP^X ⊈ +P^X, BQP/poly^X, Mod_3P^X, Mod_5P^X, SUBEXP^X, co.NP/poly^X

∃X: cocap.compNP^X ⊈ DQP^X

Likeliest blank:

∀X: compNP^X ⊆^? US^X, co.A_0PP^X, co.MA_E^X, co.QMIP^X, co.QMIP_{le}^X, co.QMIP_{ne}^X, co.RP^{PromiseUP}^X

∀X: cocap.compNP^X ⊆^? APP^X, AmpMP^X, AvgE^X, BPE^X, BQP/qpoly^X, CZK^X, C_=P^X, Check^X, HeurBPP^X, Nearly-P^X, P-Sel^X, QSZK^X, UE^X, XOR-MIP*[2,1]^X

Unlikeliest blank:

∀X: RBQP^X, compIP^X ⊆^? compNP^X

∀X: Q^X, YPP^X, ZBQP^X, cocap.compIP^X ⊆^? cocap.compNP^X

CSL: Context Sensitive Languages

CSL in the Zoo.

Best inclusions: [Kur64]

∀X: GCSL^X ⊆ CSL^X ⊆ NLINSPACE^X

∀X: PBP^X ⊆ cocap.CSL^X

Best separations:

∃X: +SAC^0^X, LIN^X, SAC^0^X ⊈ CSL^X

∃X: cocap.CSL^X ⊈ DCFL^X, L^X

Likeliest blank:

∀X: NC^0^X, co.CFL^X, cocap.1NAuxPDA^p^X ⊆^? CSL^X

∀X: cocap.CSL^X ⊆^? BPQP^X, CH^X, Coh^X, DQP^X, HeurBPP^X, Nearly-P^X, P-Sel^X, PP/poly^X, QMIP^X, QMIP_{le}^X, QMIP_{ne}^X, SQG^X, SUBEXP^X

Unlikeliest blank:

∀X: CSL^X ⊆^? AC^0/poly^X, LIN^X, QAC^0^X, QNC_f^0^X, cocap.CFL^X, cocap.R_HL^X, cocap.UL^X

CZK: Computational Zero-Knowledge

CZK in the Zoo.

Best inclusions:

∀X: CZK^X ⊆ IP^X

∀X: SZK^X ⊆ cocap.CZK^X

Best separations: [Imp..] [Imp..]

∃X: UP^X, cocap.beta_2P^X ⊈ CZK^X

Likeliest blank:

∀X: YP^X, ZBQP^X, cocap.NLIN^X, cocap.UP^X, cocap.WAPP^X, cocap.compNP^X ⊆^? CZK^X ⊆^? co.QMIP^X, co.QMIP_{le}^X, co.QMIP_{ne}^X

∀X: cocap.CZK^X ⊆^? AM[polylog]^X, CH^X, DQP^X, EH^X, NE/poly^X, PP/poly^X, QIP[2]^X

Unlikeliest blank:

∀X: CZK^X ⊆^? AC^0/poly^X, AVBPP^X, AvgE^X, BPP/log^X, BPQP^X, Check^X, IC[log,poly]^X, P-Close^X, YPP^X, cocap.C_=P^X, cocap.N.BPP^X, cocap.NISZK^X, cocap.NP/one^X, cocap.PZK^X, cocap.WAPP^X, cocap.XOR-MIP*[2,1]^X, cocap.compIP^X

∀X: NLINSPACE^X, NT*^X, Q^X, WAPP^X, YQP^X, cocap.EP^X, frIP^X ⊆^? cocap.CZK^X

DCFL: Deterministic CFL [GG66]

DCFL in the Zoo.

Best inclusions: [Coo79]

∀X: REG^X ⊆ DCFL^X ⊆ LIN^X, SC^X, cocap.CFL^X

Best separations: [GG66] [GG66]

∃X: CFL^X, cocap.CSL^X ⊈ DCFL^X ⊈ REG^X

Likeliest blank:

∀X: DCFL^X ⊆^? +L/poly^X, AL^X, QNC^1^X

Unlikeliest blank:

∀X: PBP^X, cocap.1NAuxPDA^p^X, cocap.GCSL^X ⊆^? DCFL^X

Delta_2P: P With NP Oracle

Delta_2P in the Zoo.

Best inclusions: [Ogi94] [RS98]

∀X: P^{FewP}^X, P^{NP[log^2]}^X ⊆ Delta_2P^X ⊆ P^{QMA}^X, SF_2^X, S_2P^X

Best separations: [Bei94] [CS92]

∃X: BPP^X, EQP^X ⊈ Delta_2P^X ⊈ PP^X, P^{NP[log^2]}^X

Delta_3P: P With Sigma_2P Oracle

Best inclusions:

∀X: BPP^{NP}^X, Sigma_2P^X ⊆ Delta_3P^X ⊆ cocap.Sigma_3P^X

Best separations: [Yao85]

∃X: cocap.Sigma_3P^X ⊈ Delta_3P^X

Likeliest blank:

∀X: Delta_3P^X ⊆^? SQG^X

Likeliest open: [Aar03b]

∀X: TreeBQP^X ⊆^? Delta_3P^X

Unlikeliest blank:

∀X: Delta_3P^X ⊆^? BPP^{NP}^X

Unlikeliest open: [Aar03b]

∀X: TreeBQP^X ⊆^? Delta_3P^X

DQP: Dynamical Quantum Polynomial-Time [Aar02b]

DQP in the Zoo.

Best inclusions: [Aar02b] [Aar02b] [Aar02b]

∀X: BQP^X, SZK^X ⊆ DQP^X ⊆ EXP^X

Best separations:

∃X: AvgP^X, NT^X, YP^X, cocap.NLIN^X, cocap.UP^X, cocap.beta_2P^X, cocap.compNP^X ⊈ DQP^X

Likeliest blank:

∀X: AVBPP^X, cocap.CSL^X, cocap.CZK^X, cocap.NIQSZK^X, cocap.WAPP^X, polyL^X ⊆^? DQP^X

Likeliest open:

∀X: DQP^X ⊆^? Almost-PSPACE^X, ESPACE^X, PP/poly^X, QMIP^X, QMIP_{le}^X, QMIP_{ne}^X, QRG^X

Unlikeliest blank:

∀X: DQP^X ⊆^? (NP-cap-coNP)/poly^X, AVBPP^X, AvgE^X, BPQP^X, BQP/log^X, ModP^X, Nearly-P^X, P-Sel^X, SF_2^X, S_2P^X, YQP^X, cocap.C_=P^X, cocap.NISZK^X, cocap.NP/one^X, cocap.QCMA^X, cocap.RP^{PromiseUP}^X, cocap.WAPP^X, cocap.XOR-MIP*[2,1]^X

Unlikeliest open:

∀X: DQP^X ⊆^? Almost-PSPACE^X, ESPACE^X, PP/poly^X, QMIP^X, QMIP_{le}^X, QMIP_{ne}^X, QRG^X

E: Exponential Time With Linear Exponent

E in the Zoo.

Best inclusions: [GHJ+91]

∀X: AvgP^X, NLINSPACE^X, NT^X, Q^X, SUBEXP^X ⊆ E^X ⊆ AvgE^X, EXP^X, ZPE^X, cocap.UE^X

Best separations:

∃X: ZPP^X ⊈ E^X

Unlikeliest blank:

∀X: E^X ⊆^? HeurBPP^X

EE: Double-Exponential Time With Linear Exponent

EE in the Zoo.

Best inclusions:

∀X: AvgE^X, ESPACE^X, EXP^X ⊆ EE^X ⊆ BPEE^X, EEXP^X, cocap.NEE^X

EEE: Triple-Exponential Time With Linear Exponent

EEE in the Zoo.

Best inclusions:

∀X: EESPACE^X, EEXP^X ⊆ EEE^X ⊆ cocap.NEEE^X

Best separations:

∃X: cocap.NEEXP^X ⊈ EEE^X

Likeliest blank:

∀X: cocap.MIP_{EXP}^X ⊆^? EEE^X

EESPACE: Double-Exponential Space With Linear Exponent

EESPACE in the Zoo.

Best inclusions:

∀X: BPEE^X, EXPSPACE^X, NEE^X ⊆ EESPACE^X ⊆ EEE^X

Best separations:

∃X: EEXP^X ⊈ EESPACE^X

EEXP: Double-Exponential Time

EEXP in the Zoo.

Best inclusions:

∀X: EE^X, EXPSPACE^X ⊆ EEXP^X ⊆ EEE^X, cocap.NEEXP^X

Best separations:

∃X: cocap.NEE^X ⊈ EEXP^X ⊈ EESPACE^X

EH: Exponential-Time Hierarchy With Linear Exponent

EH in the Zoo.

Best inclusions:

∀X: MA_E^X, PH^X ⊆ EH^X ⊆ ESPACE^X, EXPH^X

Best separations:

∃X: EH^X ⊈ NEXP/poly^X

Likeliest blank:

∀X: EQP^X, FH^X, NT*^X, QAC^0^X, QCFL^X, QNC^0^X, RG[1]^X, UAP^X, cocap.AM[polylog]^X, cocap.CZK^X, cocap.compIP^X ⊆^? EH^X ⊆^? NEXP^{NP}^X, PEXP^X

Unlikeliest blank:

∀X: Almost-PSPACE^X, QPSPACE^X, QRG^X ⊆^? EH^X

ELEMENTARY: Iterated Exponential Time

ELEMENTARY in the Zoo.

Best inclusions:

∀X: NEEE^X ⊆ ELEMENTARY^X ⊆ PR^X

Best separations: [HS65]

∃X: PR^X ⊈ ELEMENTARY^X

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

EP in the Zoo.

Best inclusions: [BHR00] [BHR00]

∀X: FewP^X, HalfP^X ⊆ EP^X ⊆ C_=P^X, Mod_3P^X, Mod_5P^X, NP^X, cocap.A_0PP^X

Likeliest blank:

∀X: EP^X ⊆^? co.C_=P^X

∀X: cocap.EP^X ⊆^? APP^X

Unlikeliest blank:

∀X: EP^X ⊆^? FewP^X, UAP^X

∀X: cocap.EP^X ⊆^? Nearly-P^X, cocap.CZK^X, cocap.UP^X

EQP: Exact Quantum Polynomial-Time

EQP in the Zoo.

Best inclusions: [FR98] [BB92]

∀X: HalfP^X ⊆ EQP^X ⊆ LWPP^X, ZQP^X

Best separations: [BV97]

∃X: EQP^X ⊈ Coh^X, Delta_2P^X, P/poly^X

Likeliest blank:

∀X: EQP^X ⊆^? EH^X, FH^X, HeurBPP^X, MIP^X, MIP*^X, MP^X, NE/poly^X, RG[1]^X, SF_4^X

Unlikeliest blank:

∀X: EQP^X ⊆^? AvgP^X, NT^X, QPLIN^X, polyL^X

ESPACE: Exponential Space With Linear Exponent

ESPACE in the Zoo.

Best inclusions:

∀X: EH^X, QPSPACE^X ⊆ ESPACE^X ⊆ EE^X, EXPSPACE^X

Best separations:

∃X: EXP^X ⊈ ESPACE^X ⊈ EXPH^X

Likeliest blank:

∀X: AVBPP^X, QS_2P^X, RG^X, cocap.QIP[2]^X ⊆^? ESPACE^X

Likeliest open:

∀X: DQP^X ⊆^? ESPACE^X

Unlikeliest blank:

∀X: ESPACE^X ⊆^? PEXP^X

Unlikeliest open:

∀X: DQP^X ⊆^? ESPACE^X

EXP: Exponential Time

EXP in the Zoo.

Best inclusions: [Aar02b] [KM92] [Gut05]

∀X: DQP^X, E^X, HeurBPP^X, RG^X, SQG^X ⊆ EXP^X ⊆ +EXP^X, BPEXP^X, EE^X, EXP/poly^X, cocap.NEXP^X

Best separations:

∃X: EXP^X ⊈ ESPACE^X

EXP/poly: Exponential Time With Polynomial-Size Advice

EXP/poly in the Zoo.

Best inclusions:

∀X: EXP^X, PP/poly^X ⊆ EXP/poly^X ⊆ NEXP/poly^X

Best separations:

∃X: ZPE^X, cocap.UE^X ⊈ EXP/poly^X

Likeliest blank:

∀X: Check^X, QRG^X, cocap.QMA(2)^X, cocap.XOR-MIP*[2,1]^X ⊆^? EXP/poly^X

EXP^{NP}: EXP with NP oracle

Best inclusions:

∀X: NEXP^X ⊆ EXP^{NP}^X ⊆ cocap.NEXP^{NP}^X

Best separations: [Hel86]

∃X: BPQP^X ⊈ EXP^{NP}^X ⊈ NEXP/poly^X

Likeliest blank:

∀X: Almost-PSPACE^X ⊆^? EXP^{NP}^X ⊆^? PEXP^X, SEH^X

Unlikeliest blank:

∀X: +EXP^X ⊆^? EXP^{NP}^X ⊆^? PEXP^X, SEH^X

EXPH: Exponential-Time Hierarchy

Best inclusions:

∀X: EH^X, NEXP^{NP}^X ⊆ EXPH^X ⊆ EXPSPACE^X

Best separations: [Hem89]

∃X: ESPACE^X, SEH^X ⊈ EXPH^X

Likeliest blank:

∀X: +EXP^X, PEXP^X, QPSPACE^X, cocap.IP_{EXP}^X ⊆^? EXPH^X

Unlikeliest blank:

∀X: EXPH^X ⊆^? cocap.NEXP^{NP}^X

EXPSPACE: Exponential Space

EXPSPACE in the Zoo.

Best inclusions:

∀X: +EXP^X, ESPACE^X, EXPH^X, IP_{EXP}^X, PEXP^X, SEH^X ⊆ EXPSPACE^X ⊆ EESPACE^X, EEXP^X

Best separations:

∃X: AvgE^X ⊈ EXPSPACE^X

Few: FewP With Flexible Acceptance Mechanism

Few in the Zoo.

Best inclusions: [Kob89]

∀X: FewP^X ⊆ Few^X ⊆ P^{FewP}^X

Likeliest blank:

∀X: P^{FewP}^X ⊆^? Few^X ⊆^? BPP_{path}^X, NE/poly^X, P^{NP[log^2]}^X

Unlikeliest blank:

∀X: SPP^X ⊆^? Few^X

FewL: Logspace Analogue of FewP [BDH+92]

Best inclusions:

∀X: FewUL^X ⊆ FewL^X ⊆ LFew^X

Likeliest blank:

∀X: co.UL^X ⊆^? FewL^X

∀X: cocap.FewL^X ⊆^? LogFew^X

Unlikeliest blank:

∀X: FewL^X ⊆^? co.FewUL^X

∀X: LogFew^X ⊆^? cocap.FewL^X

FewP: NP With Few Witnesses

FewP in the Zoo.

Best inclusions: [BHR00]

∀X: UP^X ⊆ FewP^X ⊆ EP^X, Few^X

Best separations: [Rub88]

∃X: FewP^X ⊈ UP^X

Likeliest blank:

∀X: FewP^X ⊆^? US^X, co.RP^{PromiseUP}^X

∀X: cocap.FewP^X ⊆^? UAP^X, UE^X

Unlikeliest blank:

∀X: EP^X ⊆^? FewP^X

FewUL: Alternate Name for LogFewNL [BJL+91]

Best inclusions:

∀X: UL^X ⊆ FewUL^X ⊆ FewL^X, LogFew^X

Likeliest blank:

∀X: cocap.FewUL^X ⊆^? UL^X

Unlikeliest blank:

∀X: co.FewL^X ⊆^? FewUL^X

∀X: UL^X ⊆^? cocap.FewUL^X

FH: Fourier Hierarchy [Shi03]

FH in the Zoo.

Best inclusions:

∀X: BPP^X ⊆ FH^X ⊆ BQP^X

Likeliest blank:

∀X: EQP^X, QAC^0^X, QCFL^X, QNC^0^X, TreeBQP^X, ZBQP^X ⊆^? FH^X ⊆^? Coh^X, EH^X, HeurBPP^X, MIP^X, MIP*^X, MP^X, NE/poly^X, RG[1]^X

Unlikeliest blank:

∀X: NIQSZK^X, WAPP^X ⊆^? FH^X ⊆^? AC^0/poly^X, BPP^X, IC[log,poly]^X, P-Close^X, YPP^X, cocap.compIP^X

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

FOLL in the Zoo.

Best inclusions:

∀X: AC^0^X ⊆ FOLL^X ⊆ AC^1^X

Best separations: [BKL+00] [BKL+00] [Smo87]

∃X: PARITY^X ⊈ FOLL^X ⊈ AC^0^X

Likeliest blank:

∀X: MAJORITY^X ⊆^? FOLL^X ⊆^? +L/poly^X, +SAC^1^X, AC^0/poly^X, AL^X, MAC^0^X, QNC^1^X, SC^X

Unlikeliest blank:

∀X: MAC^0^X ⊆^? FOLL^X ⊆^? LIN^X, MAC^0^X

frIP: Function-Restricted IP Proof Systems

frIP in the Zoo.

Best inclusions: [Yao90b] [FRS88] [BG94]

∀X: compIP^X ⊆ frIP^X ⊆ Coh^X, MIP^X

∀X: Check^X ⊆ cocap.frIP^X

Likeliest blank:

∀X: frIP^X ⊆^? co.MIP_{EXP}^X, co.NEE^X

Unlikeliest blank:

∀X: frIP^X ⊆^? AVBPP^X, AvgE^X, BPQP^X, BQP/mpoly^X, Check^X, N.BPP^X, Nearly-P^X, WAPP^X, YQP^X, cocap.AM[polylog]^X, cocap.CZK^X, cocap.C_=P^X, cocap.NIQSZK^X, cocap.QCMA^X, cocap.XOR-MIP*[2,1]^X, cocap.compIP^X

∀X: cocap.frIP^X ⊆^? AC^0/poly^X, BPP/log^X, IC[log,poly]^X, P-Close^X, YPP^X, cocap.N.BPP^X, cocap.WAPP^X

GCSL: Growing CSL [DW86]

GCSL in the Zoo.

Best inclusions: [DW86] [DW86]

∀X: CFL^X ⊆ GCSL^X ⊆ CSL^X, Q^X, SAC^1^X

Likeliest blank:

∀X: cocap.GCSL^X ⊆^? 1NAuxPDA^p^X, NLIN^X, QCFL^X

Unlikeliest blank:

∀X: co.SAC^0^X ⊆^? GCSL^X ⊆^? 3-PBP^X

∀X: QCFL^X ⊆^? cocap.GCSL^X ⊆^? DCFL^X

HalfP: RP With Exactly Half Acceptance [BB92]

HalfP in the Zoo.

Best inclusions: [BB92]

∀X: HalfP^X ⊆ EP^X, EQP^X, RP^X

∀X: P^X ⊆ cocap.HalfP^X

Likeliest blank:

∀X: HalfP^X ⊆^? US^X, YPP^X, co.NE^X, co.NP/log^X, co.RP^{PromiseUP}^X

∀X: cocap.HalfP^X ⊆^? +P^X, AvgE^X, IC[log,poly]^X, Nearly-P^X, P-Sel^X, UE^X, compIP^X

Unlikeliest blank:

∀X: HalfP^X ⊆^? AL^X, NC^X, SC^X, cocap.NLIN^X

HeurBPP: Heuristic BPP

HeurBPP in the Zoo.

Best inclusions:

∀X: AVBPP^X, AvgP^X ⊆ HeurBPP^X ⊆ EXP^X

Best separations:

∃X: cocap.UP^X ⊈ HeurBPP^X

Likeliest blank:

∀X: EQP^X, FH^X, NT^X, QAC^0^X, QCFL^X, QNC^0^X, TreeBQP^X, YP^X, ZBQP^X, cocap.CSL^X, cocap.NISZK^X, cocap.NLIN^X, cocap.PZK^X, cocap.WAPP^X, cocap.beta_2P^X, cocap.compNP^X, polyL^X ⊆^? HeurBPP^X

Unlikeliest blank:

∀X: E^X ⊆^? HeurBPP^X ⊆^? AvgE^X, BPE^X, Coh^X, Nearly-P^X

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

IC[log,poly] in the Zoo.

Best inclusions:

∀X: P/log^X ⊆ IC[log,poly]^X ⊆ P/poly^X

Best separations:

∃X: L/poly^X ⊈ IC[log,poly]^X ⊈ BQP/log^X, NP/log^X

Likeliest blank:

∀X: TALLY^X, cocap.HalfP^X, cocap.RNC^X ⊆^? IC[log,poly]^X ⊆^? BPP//log^X, BQP/qlog^X

Unlikeliest blank:

∀X: AVBPP^X, AmpP-BQP^X, BPP//log^X, CZK^X, FH^X, P-Close^X, P-Sel^X, RBQP^X, TC^0/poly^X, WAPP^X, XOR-MIP*[2,1]^X, YPP^X, cocap.frIP^X ⊆^? IC[log,poly]^X ⊆^? BPP/mlog^X

IP: Interactive Proof

IP in the Zoo.

Best inclusions:

∀X: AM[polylog]^X, CZK^X, compIP^X ⊆ IP^X ⊆ MIP^X, MIP*^X, PSPACE^X, QIP^X

Best separations: [AGH90]

∃X: IP^X ⊈ AM[polylog]^X

Unlikeliest blank:

∀X: QMIP^X, QMIP_{le}^X, QMIP_{ne}^X ⊆^? IP^X

IP_{EXP}: Exponential Time Interactive Proof

Best inclusions:

∀X: AM_{EXP}^X ⊆ IP_{EXP}^X ⊆ EXPSPACE^X, MIP_{EXP}^X

Likeliest blank:

∀X: cocap.IP_{EXP}^X ⊆^? EXPH^X

L: Logarithmic Space

L in the Zoo.

Best inclusions: [Bor77]

∀X: NC^1^X, PBP^X ⊆ L^X ⊆ cocap.R_HL^X, cocap.UL^X

Best separations:

∃X: cocap.CSL^X ⊈ L^X ⊈ LIN^X

Unlikeliest blank:

∀X: AC^1^X ⊆^? L^X

L/poly: Nonuniform Logarithmic Space

L/poly in the Zoo.

Best inclusions:

∀X: BPL^X, TC^0/poly^X ⊆ L/poly^X ⊆ NL/poly^X

Best separations:

∃X: L/poly^X ⊈ IC[log,poly]^X

Likeliest blank:

∀X: cocap.UL^X ⊆^? L/poly^X

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

Best inclusions: [CKS81] [BCP83] [BCP83]

∀X: PL^X ⊆ L^{DET}^X ⊆ AL^X, NC^2^X

Likeliest blank:

∀X: +L^X ⊆^? L^{DET}^X ⊆^? PL^X

LFew: Logspace Analogue of Few [ARZ99]

Best inclusions: [ARZ99] [ARZ99]

∀X: FewL^X, LogFew^X ⊆ LFew^X ⊆ NL^X, SPL^X

LIN: Linear Time

LIN in the Zoo.

Best inclusions:

∀X: DCFL^X ⊆ LIN^X ⊆ P^X, cocap.NLIN^X

Best separations:

∃X: L^X ⊈ LIN^X ⊈ CSL^X, QCFL^X

Likeliest blank:

∀X: MAJORITY^X ⊆^? LIN^X ⊆^? QNC^X, polyL^X

Unlikeliest blank:

∀X: 1NAuxPDA^p^X, CSL^X, FOLL^X, QCFL^X, QNC^1^X ⊆^? LIN^X ⊆^? +SAC^0^X, cocap.1NAuxPDA^p^X

LogFew: Logspace-Bounded Few [BDH+92]

LogFew in the Zoo.

Best inclusions:

∀X: FewUL^X ⊆ LogFew^X ⊆ LFew^X

Likeliest blank:

∀X: cocap.FewL^X ⊆^? LogFew^X

Unlikeliest blank:

∀X: LogFew^X ⊆^? cocap.FewL^X

LWPP: Length-Dependent Wide PP [FFK94]

LWPP in the Zoo.

Best inclusions: [FR98]

∀X: EQP^X, SPP^X ⊆ LWPP^X ⊆ WPP^X

Best separations: [STT05]

∃X: WPP^X ⊈ LWPP^X

Unlikeliest blank:

∀X: Mod_3P^X, Mod_5P^X, compIP^X ⊆^? LWPP^X ⊆^? UAP^X

MA: Merlin-Arthur

MA in the Zoo.

Best inclusions: [BGM02] [RS98]

∀X: N.BPP^X ⊆ MA^X ⊆ MA_E^X, QCMA^X, SBP^X, S_2P^X

∀X: YPP^X ⊆ cocap.MA^X

Best separations: [FFK+93]

∃X: BQP^X ⊈ MA^X ⊈ N.BPP^X

MA_E: Exponential-Time MA With Linear Exponent

MA_E in the Zoo.

Best inclusions:

∀X: MA^X, NE^X ⊆ MA_E^X ⊆ EH^X, MA_{EXP}^X

∀X: BPE^X ⊆ cocap.MA_E^X

Best separations:

∃X: co.UP^X ⊈ MA_E^X

Likeliest blank:

∀X: TreeBQP^X, co.RBQP^X, co.compNP^X, cocap.NISZK^X, cocap.PZK^X, cocap.WAPP^X ⊆^? MA_E^X

Unlikeliest blank:

∀X: QMIP^X, QMIP_{le}^X, QMIP_{ne}^X ⊆^? MA_E^X

∀X: cocap.QMIP^X, cocap.QMIP_{le}^X, cocap.QMIP_{ne}^X ⊆^? cocap.MA_E^X

MA_{EXP}: Exponential-Time MA

MA_{EXP} in the Zoo.

Best inclusions: [Ver92]

∀X: MA_E^X, NEXP^X ⊆ MA_{EXP}^X ⊆ AM_{EXP}^X, PEXP^X, cocap.NEXP^{NP}^X

∀X: BPEXP^X ⊆ cocap.MA_{EXP}^X

MAC^0: Majority of AC^0

MAC^0 in the Zoo.

Best inclusions:

∀X: AC^0^X, MAJORITY^X ⊆ MAC^0^X ⊆ TC^0^X

Best separations:

∃X: PARITY^X ⊈ MAC^0^X

Likeliest blank:

∀X: FOLL^X ⊆^? MAC^0^X

Unlikeliest blank:

∀X: FOLL^X ⊆^? MAC^0^X ⊆^? FOLL^X

MAJORITY: Majority or Minority of Input Bits

Best inclusions:

∀X: NONE^X ⊆ MAJORITY^X ⊆ (k>=5)-PBP^X, MAC^0^X, PT_1^X, cocap.CFL^X

Best separations: [Raz87]

∃X: MAJORITY^X ⊈ AC^0[2]^X, PL_1^X, QNC^0^X, REG^X

Likeliest blank:

∀X: MAJORITY^X ⊆^? AC^0/poly^X, FOLL^X, LIN^X, QACC^0^X

Unlikeliest blank:

∀X: QNC^0^X, cocap.SAC^0^X ⊆^? MAJORITY^X

MIP: Multi-Prover Interactive Proof

MIP in the Zoo.

Best inclusions: [FRS88]

∀X: IP^X, frIP^X ⊆ MIP^X ⊆ QMIP_{ne}^X

Likeliest blank:

∀X: EQP^X, FH^X, QAC^0^X, QCFL^X, QNC^0^X, TreeBQP^X, co.RBQP^X ⊆^? MIP^X

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

Best inclusions:

∀X: IP^X, XOR-MIP*[2,1]^X ⊆ MIP*^X ⊆ QMIP^X

Likeliest blank:

∀X: EQP^X, FH^X, QAC^0^X, QCFL^X, QNC^0^X, TreeBQP^X, co.RBQP^X ⊆^? MIP*^X

∀X: cocap.MIP*^X ⊆^? AH^X, NEXP/poly^X

Unlikeliest blank:

∀X: NP/poly^X ⊆^? MIP*^X

∀X: BQP/qpoly^X, Coh^X, P-Sel^X, PL_{infty}^X, cocap.NP/poly^X ⊆^? cocap.MIP*^X

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

MIP_{EXP} in the Zoo.

Best inclusions:

∀X: IP_{EXP}^X ⊆ MIP_{EXP}^X ⊆ NEEXP^X

Best separations:

∃X: AvgE^X, QPSPACE^X, co.UE^X ⊈ MIP_{EXP}^X

Likeliest blank:

∀X: co.QMA(2)^X, co.XOR-MIP*[2,1]^X, co.frIP^X ⊆^? MIP_{EXP}^X ⊆^? co.NEEE^X

∀X: cocap.MIP_{EXP}^X ⊆^? EEE^X

Unlikeliest blank:

∀X: MIP_{EXP}^X ⊆^? AM_{EXP}^X, NE/poly^X, cocap.NEXP^{NP}^X

∀X: cocap.MIP_{EXP}^X ⊆^? cocap.AM_{EXP}^X

Mod_3P: Mod-3 Polynomial-Time

Best inclusions:

∀X: EP^X, SPP^X ⊆ Mod_3P^X ⊆ ModP^X, SF_3^X

Best separations: [BBF98]

∃X: Mod_5P^X, NT^X, ZPP^X, compNP^X ⊈ Mod_3P^X ⊈ +P^X, Mod_5P^X, PH^X

Likeliest blank:

∀X: Mod_3P^X ⊆^? PP/poly^X, SF_2^X

Unlikeliest blank:

∀X: C_=P^X ⊆^? Mod_3P^X ⊆^? LWPP^X

Mod_5P: Mod-5 Polynomial-Time

Best inclusions:

∀X: EP^X, SPP^X ⊆ Mod_5P^X ⊆ ModP^X

Best separations: [BBF98]

∃X: Mod_3P^X, NT^X, ZPP^X, compNP^X ⊈ Mod_5P^X ⊈ +P^X, Mod_3P^X, PH^X

Likeliest blank:

∀X: Mod_5P^X ⊆^? PP/poly^X, SF_4^X

Unlikeliest blank:

∀X: C_=P^X ⊆^? Mod_5P^X ⊆^? LWPP^X

ModP: Mod_kP With Arbitrary k [KT96]

ModP in the Zoo.

Best inclusions: [KT96]

∀X: +P^X, Mod_3P^X, Mod_5P^X ⊆ ModP^X ⊆ AmpMP^X

Likeliest blank:

∀X: AmpMP^X ⊆^? ModP^X

Unlikeliest blank:

∀X: AVBPP^X, Almost-PSPACE^X, DQP^X, QMIP^X, QMIP_{le}^X, QMIP_{ne}^X, QRG^X ⊆^? ModP^X

MP: Middle-Bit P [GKR+95]

MP in the Zoo.

Best inclusions: [Tod89]

∀X: AmpMP^X, PH^X ⊆ MP^X ⊆ P^{#P[1]}^X

Likeliest blank:

∀X: EQP^X, FH^X, QAC^0^X, QCFL^X, QNC^0^X ⊆^? MP^X

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

Best inclusions:

∀X: P^{PP}^X ⊆ MP^{#P}^X ⊆ CH^X

Likeliest blank:

∀X: SF_2^X, cocap.QAM^X ⊆^? MP^{#P}^X

Likeliest open:

∀X: MP^{#P}^X ⊆^? P^{PP}^X

Unlikeliest open:

∀X: MP^{#P}^X ⊆^? P^{PP}^X

N.BPP: BPP With Existential Operator

N.BPP in the Zoo.

Best inclusions:

∀X: NP^X ⊆ N.BPP^X ⊆ MA^X, N.NISZK^X

∀X: BPP^X ⊆ cocap.N.BPP^X

Best separations: [FFK+93]

∃X: MA^X ⊈ N.BPP^X

Likeliest blank:

∀X: cocap.N.BPP^X ⊆^? (NP-cap-coNP)/poly^X

Unlikeliest blank:

∀X: N.NISZK^X, frIP^X ⊆^? N.BPP^X

∀X: CZK^X, RQP^X, cocap.N.NISZK^X, cocap.SBP^X, cocap.frIP^X ⊆^? cocap.N.BPP^X

N.NISZK: NISZK With Existential Operator

N.NISZK in the Zoo.

Best inclusions:

∀X: N.BPP^X, NISZK^X ⊆ N.NISZK^X ⊆ NP/poly^X, Sigma_2P^X

Likeliest blank:

∀X: YPP^X, co.NISZK^X, cocap.NISZK_h^X, cocap.PZK^X, cocap.WAPP^X ⊆^? N.NISZK^X ⊆^? co.Sigma_2P^X

∀X: cocap.N.NISZK^X ⊆^? BPP^{NP}^X, QMIP^X, QMIP_{le}^X, QMIP_{ne}^X

Unlikeliest blank:

∀X: QMA(2)^X, co.WAPP^X ⊆^? N.NISZK^X ⊆^? N.BPP^X, NP/one^X, WAPP^X, XOR-MIP*[2,1]^X, co.C_=P^X

∀X: cocap.QMIP^X, cocap.QMIP_{le}^X, cocap.QMIP_{ne}^X ⊆^? cocap.N.NISZK^X ⊆^? (NP-cap-coNP)/poly^X, cocap.C_=P^X, cocap.N.BPP^X, cocap.NIQSZK^X, cocap.NP/one^X, cocap.WAPP^X, cocap.XOR-MIP*[2,1]^X

NC: Nick's Class

NC in the Zoo.

Best inclusions: [Bor77]

∀X: NC^2^X ⊆ NC^X ⊆ P^X, cocap.RNC^X, polyL^X

Best separations:

∃X: NC^X ⊈ NC^2^X

Unlikeliest blank:

∀X: HalfP^X, QNC^X ⊆^? NC^X

NC^0: Level 0 of NC

NC^0 in the Zoo.

Best inclusions:

∀X: NONE^X ⊆ NC^0^X ⊆ +SAC^0^X, PL_1^X, QNC^0^X, cocap.SAC^0^X

Best separations:

∃X: NC^0^X ⊈ 2-PBP^X, SPARSE^X

Likeliest blank:

∀X: NC^0^X ⊆^? 1NAuxPDA^p^X, CSL^X, Q^X, QCFL^X

Unlikeliest blank:

∀X: QNC^0^X, cocap.SAC^0^X ⊆^? NC^0^X

NC^1: Level 1 of NC

NC^1 in the Zoo.

Best inclusions: [Bor77] [Bar89]

∀X: (k>=5)-PBP^X, REG^X, TC^0^X ⊆ NC^1^X ⊆ L^X, QNC^1^X

Best separations: [Mil92]

∃X: AC^1^X ⊈ NC^1^X

NC^2: Level 2 of NC

NC^2 in the Zoo.

Best inclusions: [BCP83]

∀X: +SAC^1^X, AC^1^X, L^{DET}^X ⊆ NC^2^X ⊆ NC^X

Best separations:

∃X: NC^X ⊈ NC^2^X ⊈ AC^1^X

Unlikeliest blank:

∀X: NC^2^X ⊆^? BPL^X, SPL^X

NE: Nondeterministic E

NE in the Zoo.

Best inclusions:

∀X: NP^X, RPE^X, UE^X ⊆ NE^X ⊆ MA_E^X, NE/poly^X, NEXP^X

Best separations:

∃X: BPP^X ⊈ NE^X

Likeliest blank:

∀X: YPP^X, co.HalfP^X, co.RNC^X ⊆^? NE^X

NE/poly: Nonuniform NE

NE/poly in the Zoo.

Best inclusions:

∀X: NE^X, NP/poly^X ⊆ NE/poly^X ⊆ NEXP/poly^X

Likeliest blank:

∀X: AVBPP^X, Check^X, EQP^X, FH^X, Few^X, NT*^X, QAC^0^X, QCFL^X, QNC^0^X, TreeBQP^X, UAP^X, cocap.AM[polylog]^X, cocap.CZK^X, cocap.RP^{PromiseUP}^X, cocap.US^X, cocap.XOR-MIP*[2,1]^X, cocap.compIP^X ⊆^? NE/poly^X

Unlikeliest blank:

∀X: MIP_{EXP}^X, NEXP/poly^X, PEXP^X, QPSPACE^X, SEH^X ⊆^? NE/poly^X

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

Nearly-P in the Zoo.

Best inclusions:

∀X: AvgP^X, P-Close^X ⊆ Nearly-P^X ⊆ ALL^X

Best separations:

∃X: Coh^X, UP^X, cocap.NLIN^X, cocap.beta_2P^X ⊈ Nearly-P^X ⊈ NEXP/poly^X

Likeliest blank:

∀X: AC^0/poly^X, NT^X, P-Sel^X, P/log^X, PL_1^X, QAC^0^X, QCFL^X, QNC^0^X, cocap.CSL^X, cocap.HalfP^X, cocap.RNC^X, cocap.UP^X, cocap.compNP^X, polyL^X ⊆^? Nearly-P^X

Unlikeliest blank:

∀X: BQP/qpoly^X, DQP^X, HeurBPP^X, PL_{infty}^X, QSZK^X, cocap.EP^X, frIP^X ⊆^? Nearly-P^X ⊆^? Coh^X

NEE: Nondeterministic EE

NEE in the Zoo.

Best inclusions:

∀X: NEXP^X ⊆ NEE^X ⊆ EESPACE^X, NEEXP^X

∀X: EE^X ⊆ cocap.NEE^X

Best separations:

∃X: +EXP^X, BPEXP^X, co.NEXP^X ⊈ NEE^X ⊈ co.NEEXP^X

∃X: cocap.NEE^X ⊈ EEXP^X

Likeliest blank:

∀X: Almost-PSPACE^X, co.QMA(2)^X, co.XOR-MIP*[2,1]^X, co.frIP^X ⊆^? NEE^X

NEEE: Nondeterministic EEE

NEEE in the Zoo.

Best inclusions:

∀X: NEEXP^X ⊆ NEEE^X ⊆ ELEMENTARY^X

∀X: EEE^X ⊆ cocap.NEEE^X

Best separations:

∃X: co.NEEXP^X ⊈ NEEE^X

Likeliest blank:

∀X: co.MIP_{EXP}^X ⊆^? NEEE^X

NEEXP: Nondeterministic EEXP

NEEXP in the Zoo.

Best inclusions:

∀X: MIP_{EXP}^X, NEE^X ⊆ NEEXP^X ⊆ NEEE^X

∀X: EEXP^X ⊆ cocap.NEEXP^X

Best separations:

∃X: BPEE^X, co.NEE^X ⊈ NEEXP^X ⊈ co.NEEE^X

∃X: cocap.NEEXP^X ⊈ EEE^X

NEXP: Nondeterministic EXP

NEXP in the Zoo.

Best inclusions: [KM02] [KM02]

∀X: NE^X, QMIP_{le}^X, QMIP_{ne}^X ⊆ NEXP^X ⊆ EXP^{NP}^X, MA_{EXP}^X, NEE^X, NEXP/poly^X, SEH^X

∀X: EXP^X, QRG^X ⊆ cocap.NEXP^X

Best separations:

∃X: co.RPE^X ⊈ NEXP^X ⊈ co.NEE^X

∃X: cocap.NEXP^X ⊈ BPEE^X

NEXP/poly: Nonuniform NEXP

NEXP/poly in the Zoo.

Best inclusions:

∀X: EXP/poly^X, NE/poly^X, NEXP^X ⊆ NEXP/poly^X ⊆ ALL^X

Best separations:

∃X: +EXP^X, AvgE^X, Coh^X, EH^X, EXP^{NP}^X, Nearly-P^X, PL_{infty}^X ⊈ NEXP/poly^X

Likeliest blank:

∀X: Almost-PSPACE^X, BPQP^X, P-Sel^X, SEH^X, cocap.MIP*^X ⊆^? NEXP/poly^X

Unlikeliest blank:

∀X: NEXP/poly^X ⊆^? NE/poly^X

NEXP^{NP}: NEXP with NP oracle

Best inclusions:

∀X: co.AM_{EXP}^X ⊆ NEXP^{NP}^X ⊆ EXPH^X

∀X: EXP^{NP}^X, MA_{EXP}^X ⊆ cocap.NEXP^{NP}^X

Likeliest blank:

∀X: AM_{EXP}^X, EH^X ⊆^? NEXP^{NP}^X

Unlikeliest blank:

∀X: EXPH^X, MIP_{EXP}^X, PEXP^X, QPSPACE^X ⊆^? cocap.NEXP^{NP}^X

NIQSZK: Non-Interactive QSZK

NIQSZK in the Zoo.

Best inclusions:

∀X: NISZK^X ⊆ NIQSZK^X ⊆ QSZK^X

∀X: BQP^X ⊆ cocap.NIQSZK^X

Likeliest blank:

∀X: co.NISZK^X, cocap.NISZK_h^X, cocap.PZK^X ⊆^? NIQSZK^X

∀X: cocap.NIQSZK^X ⊆^? CH^X, DQP^X, PP/poly^X

Unlikeliest blank:

∀X: NIQSZK^X ⊆^? FH^X, QAC^0^X, QNC_f^0^X, TreeBQP^X, ZQP^X

∀X: NLINSPACE^X, NT*^X, Q^X, cocap.N.NISZK^X, cocap.QMIP^X, cocap.QMIP_{le}^X, cocap.QMIP_{ne}^X, frIP^X ⊆^? cocap.NIQSZK^X

NISZK: Non-Interactive SZK [DDP+98]

NISZK in the Zoo.

Best inclusions: [BG03]

∀X: NISZK^X ⊆ N.NISZK^X, NIQSZK^X, NISZK_h^X

∀X: BPP^X ⊆ cocap.NISZK^X

Likeliest blank:

∀X: NISZK^X ⊆^? co.N.NISZK^X, co.NIQSZK^X, co.NISZK_h^X

∀X: cocap.NISZK^X ⊆^? (NP-cap-coNP)/poly^X, BQP/qpoly^X, Coh^X, HeurBPP^X, MA_E^X, PP^X, PZK^X, QMA(2)^X, QS_2P^X, RG[1]^X, XOR-MIP*[2,1]^X

Unlikeliest blank:

∀X: NISZK^X ⊆^? BPP^X

∀X: CZK^X, DQP^X, QSZK^X, polyL^X ⊆^? cocap.NISZK^X

NISZK_h: NISZK With Limited Help [BG03]

NISZK_h in the Zoo.

Best inclusions: [BG03] [BG03]

∀X: NISZK^X ⊆ NISZK_h^X ⊆ SZK^X

Best separations: [Aar02]

∃X: NISZK_h^X ⊈ BQP^X

Likeliest blank:

∀X: TreeBQP^X, co.NISZK^X, cocap.PZK^X ⊆^? NISZK_h^X

∀X: cocap.NISZK_h^X ⊆^? N.NISZK^X, NIQSZK^X

Unlikeliest blank:

∀X: NISZK_h^X ⊆^? cocap.PZK^X

∀X: cocap.NISZK_h^X ⊆^? BPP^X, QAC^0^X, QNC_f^0^X, ZQP^X

NL: Nondeterministic Logarithmic-Space

NL in the Zoo.

Best inclusions: [Sud78] [ARZ99]

∀X: LFew^X, RL^X ⊆ NL^X ⊆ NL/poly^X, SAC^1^X, cocap.C_=L^X

NL/poly: Nonuniform NL

NL/poly in the Zoo.

Best inclusions: [GW96]

∀X: L/poly^X, NL^X ⊆ NL/poly^X ⊆ +L/poly^X

Likeliest blank:

∀X: SPL^X ⊆^? NL/poly^X

NLIN: Nondeterministic LIN

NLIN in the Zoo.

Best inclusions:

∀X: CFL^X ⊆ NLIN^X ⊆ NLINSPACE^X, Q^X

∀X: LIN^X ⊆ cocap.NLIN^X

Best separations:

∃X: cocap.NLIN^X ⊈ DQP^X, Nearly-P^X

Likeliest blank:

∀X: cocap.GCSL^X ⊆^? NLIN^X ⊆^? US^X, co.A_0PP^X, co.NP/poly^X, co.QMIP^X, co.QMIP_{le}^X, co.QMIP_{ne}^X, co.RP^{PromiseUP}^X

∀X: cocap.NLIN^X ⊆^? APP^X, AmpMP^X, BPQP^X, BQP/qpoly^X, CZK^X, C_=P^X, Coh^X, HeurBPP^X, P-Sel^X, QSZK^X, SUBEXP^X, XOR-MIP*[2,1]^X

Unlikeliest blank:

∀X: betaP^X, compIP^X ⊆^? NLIN^X

∀X: HalfP^X, NLINSPACE^X, Q^X, QNC^X, cocap.betaP^X, cocap.compIP^X ⊆^? cocap.NLIN^X

NLINSPACE: Nondeterministic Linear Space

Best inclusions: [Kur64]

∀X: CSL^X, NLIN^X, polyL^X ⊆ NLINSPACE^X ⊆ E^X, PSPACE^X

Likeliest blank:

∀X: AL^X, cocap.Q^X ⊆^? NLINSPACE^X

Unlikeliest blank:

∀X: NT*^X ⊆^? NLINSPACE^X ⊆^? AVBPP^X, BQP/mpoly^X, NT^X, YQP^X, cocap.CZK^X, cocap.NIQSZK^X, cocap.NLIN^X, cocap.UP^X, cocap.WAPP^X, cocap.XOR-MIP*[2,1]^X, cocap.beta_2P^X, polyL^X

NONE: The Empty Class

NONE in the Zoo.

Best inclusions:

∀X: NONE^X ⊆ MAJORITY^X, NC^0^X, PARITY^X, TALLY^X

NP: Nondeterministic Polynomial-Time

NP in the Zoo.

Best inclusions: [VV86]

∀X: EP^X, Q^X, RBQP^X, betaP^X, compNP^X ⊆ NP^X ⊆ N.BPP^X, NE^X, NP/one^X, RP^{PromiseUP}^X, co.US^X

∀X: YP^X ⊆ cocap.NP^X ⊆ (NP-cap-coNP)/poly^X

Best separations:

∃X: co.RP^X ⊈ NP^X ⊈ C_=P^X

Unlikeliest blank:

∀X: NP^X ⊆^? UE^X

∀X: cocap.NP^X ⊆^? cocap.UE^X

NP/log: NP With Logarithmic Advice

NP/log in the Zoo.

Best inclusions:

∀X: NP/one^X ⊆ NP/log^X ⊆ NP/poly^X

∀X: P/log^X ⊆ cocap.NP/log^X

Best separations:

∃X: BQP/qlog^X, IC[log,poly]^X, P-Sel^X, SPARSE^X, co.SPARSE^X ⊈ NP/log^X

Likeliest blank:

∀X: YPP^X, co.HalfP^X, co.RNC^X ⊆^? NP/log^X

Unlikeliest blank:

∀X: NP/log^X ⊆^? NP/one^X

∀X: cocap.NP/log^X ⊆^? cocap.NP/one^X

NP/one: NP With One Bit of Advice

Best inclusions:

∀X: NP^X ⊆ NP/one^X ⊆ NP/log^X

∀X: TALLY^X ⊆ cocap.NP/one^X

Best separations: [FFK+93]

∃X: cocap.NP/one^X ⊈ (NP-cap-coNP)/poly^X

Likeliest blank:

∀X: P/log^X ⊆^? NP/one^X

Unlikeliest blank:

∀X: N.NISZK^X, NP/log^X, QMIP^X, QMIP_{le}^X, QMIP_{ne}^X ⊆^? NP/one^X

∀X: AVBPP^X, BPP//log^X, BQP/mlog^X, CZK^X, DQP^X, WAPP^X, XOR-MIP*[2,1]^X, cocap.N.NISZK^X, cocap.NP/log^X, cocap.QMIP^X, cocap.QMIP_{le}^X, cocap.QMIP_{ne}^X ⊆^? cocap.NP/one^X

NP/poly: Nonuniform NP

NP/poly in the Zoo.

Best inclusions: [BM88]

∀X: AM^X, N.NISZK^X, NP/log^X ⊆ NP/poly^X ⊆ NE/poly^X, PP/poly^X

∀X: (NP-cap-coNP)/poly^X ⊆ cocap.NP/poly^X

Best separations:

∃X: NT^X, co.UP^X, co.beta_2P^X, co.compNP^X ⊈ NP/poly^X

Likeliest blank:

∀X: co.NLIN^X, co.RBQP^X, co.WAPP^X ⊆^? NP/poly^X

Unlikeliest blank:

∀X: NP/poly^X ⊆^? MIP*^X

∀X: cocap.NP/poly^X ⊆^? cocap.MIP*^X

NT: Near-Testable [GHJ+91]

NT in the Zoo.

Best inclusions: [GHJ+91] [GHJ+91]

∀X: P^X ⊆ NT^X ⊆ E^X, NT*^X

Best separations:

∃X: NT^X ⊈ BQP/poly^X, DQP^X, Mod_3P^X, Mod_5P^X, NP/poly^X, PH^X, PP^X, SUBEXP^X

Likeliest blank:

∀X: NT^X ⊆^? BPQP^X, Coh^X, HeurBPP^X, Nearly-P^X, P-Sel^X, PP/poly^X, QMIP^X, QMIP_{le}^X, QMIP_{ne}^X, SQG^X

Unlikeliest blank:

∀X: EQP^X, NLINSPACE^X, NT*^X, Q^X, betaP^X, cocap.compIP^X ⊆^? NT^X

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

NT* in the Zoo.

Best inclusions: [GHJ+91] [GHJ+91]

∀X: NT^X ⊆ NT*^X ⊆ +P^X

Likeliest blank:

∀X: cocap.UP^X ⊆^? NT*^X ⊆^? AvgE^X, EH^X, NE/poly^X

Unlikeliest blank:

∀X: +P^X, C_=P^X ⊆^? NT*^X ⊆^? AVBPP^X, AvgP^X, BPQP^X, BQP/mpoly^X, Check^X, NLINSPACE^X, NT^X, cocap.AM[polylog]^X, cocap.CZK^X, cocap.NIQSZK^X, cocap.QAM^X, cocap.QMA(2)^X, cocap.XOR-MIP*[2,1]^X, cocap.compIP^X