Containment relations between complexity classes

This file collects the standard containment results between complexity classes.

Theorems

• DTIME_subset_NTIME — DTIME(T) ⊆ NTIME(T)
• P_subset_NP — P ⊆ NP
• DTIME_mono — T₁ =O T₂ → DTIME(T₁) ⊆ DTIME(T₂)
• NTIME_mono — T₁ =O T₂ → NTIME(T₁) ⊆ NTIME(T₂)
• DSPACE_mono — S₁ =O S₂ → DSPACE(S₁) ⊆ DSPACE(S₂)
• P_subset_EXP — P ⊆ EXP
• DTIME_subset_DSPACE — DTIME(T) ⊆ DSPACE(T) (time bounds space)
• P_subset_PSPACE — P ⊆ PSPACE
• RTIME_subset_NTIME — RTIME(T) ⊆ NTIME(T) (one-sided error → nondeterministic)
• RP_subset_NP — RP ⊆ NP
• DTIME_subset_BPTIME — DTIME(T) ⊆ BPTIME(T) (deterministic → zero-error probabilistic)
• P_subset_BPP — P ⊆ BPP
• NP_subset_NEXP — NP ⊆ NEXP
• EXP_subset_NEXP — EXP ⊆ NEXP
• BPTIME_subset_PPTIME — BPTIME(T) ⊆ PPTIME(T) (bounded error → unbounded error)
• BPP_subset_PP — BPP ⊆ PP
• P_compl — L ∈ P → Lᶜ ∈ P (P closed under complement)
• DSPACE_subset_NSPACE — DSPACE(S) ⊆ NSPACE(S)
• NSPACE_mono — S₁ =O S₂ → NSPACE(S₁) ⊆ NSPACE(S₂)
• L_subset_NL — L ⊆ NL
• ZPP_subset_RP — ZPP ⊆ RP
• ZPP_subset_coRP — ZPP ⊆ coRP
• DTIME_subset_NSPACE — DTIME(T) ⊆ NSPACE(T)
• P_subset_NPSPACE — P ⊆ NPSPACE
• P_subset_NEXP — P ⊆ NEXP
• P_subset_PP — P ⊆ PP
• P_union — L₁ ∈ P → L₂ ∈ P → L₁ ∪ L₂ ∈ P (P closed under union)
• P_inter — L₁ ∈ P → L₂ ∈ P → L₁ ∩ L₂ ∈ P (P closed under intersection)

theorem Complexity.DTIME_subset_NTIME (T : ℕ → ℕ) : DTIME T ⊆ NTIME T

DTIME ⊆ NTIME: every language decidable by a DTM in time O(T) is also decidable by an NTM in time O(T), via the TM.toNTM embedding.

theorem Complexity.P_subset_NP : P ⊆ NP

P ⊆ NP

theorem Complexity.DTIME_mono {T₁ T₂ : ℕ → ℕ} (h : BigO T₁ T₂) : DTIME T₁ ⊆ DTIME T₂

DTIME is monotone with respect to =O: if T₁ =O T₂, then DTIME T₁ ⊆ DTIME T₂.

theorem Complexity.P_subset_EXP : P ⊆ EXP

P ⊆ EXP: every polynomial-time language is also exponential-time.

theorem Complexity.DTIME_subset_DSPACE (T : ℕ → ℕ) : DTIME T ⊆ DSPACE T

DTIME ⊆ DSPACE: a DTM running in time T uses at most O(T) auxiliary space, since every two-way tape head can move at most one cell per step.

theorem Complexity.P_subset_PSPACE : P ⊆ PSPACE

P ⊆ PSPACE: every polynomial-time language uses polynomial space.

theorem Complexity.RTIME_subset_NTIME (T : ℕ → ℕ) : RTIME T ⊆ NTIME T

RTIME ⊆ NTIME: one-sided error implies nondeterministic. The same NTM works: RejectsWithProb 0 means no accepting paths for x ∉ L, and AcceptsWithProb (1/2) means some accepting path exists for x ∈ L.

theorem Complexity.RP_subset_NP : RP ⊆ NP

RP ⊆ NP.

theorem Complexity.DTIME_subset_BPTIME (T : ℕ → ℕ) : DTIME T ⊆ BPTIME T

DTIME ⊆ BPTIME: every deterministic TM can be viewed as a PTM with zero error. When the DTM accepts, all paths accept (prob = 1 ≥ 2/3). When it rejects, no path accepts (prob = 0 ≤ 1/3).

theorem Complexity.P_subset_BPP : P ⊆ BPP

P ⊆ BPP: every polynomial-time language is also in BPP.

theorem Complexity.NTIME_mono {T₁ T₂ : ℕ → ℕ} (h : BigO T₁ T₂) : NTIME T₁ ⊆ NTIME T₂

NTIME is monotone: if T₁ =O T₂, then NTIME T₁ ⊆ NTIME T₂.

theorem Complexity.DSPACE_mono {S₁ S₂ : ℕ → ℕ} (h : BigO S₁ S₂) : DSPACE S₁ ⊆ DSPACE S₂

DSPACE is monotone: if S₁ =O S₂, then DSPACE S₁ ⊆ DSPACE S₂.

theorem Complexity.NP_subset_NEXP : NP ⊆ NEXP

NP ⊆ NEXP: every nondeterministic polynomial-time language is also nondeterministic exponential-time.

theorem Complexity.EXP_subset_NEXP : EXP ⊆ NEXP

EXP ⊆ NEXP: every deterministic exponential-time language is also nondeterministic exponential-time.

theorem Complexity.BPTIME_subset_PPTIME (T : ℕ → ℕ) : BPTIME T ⊆ PPTIME T

BPTIME ⊆ PPTIME: two-sided bounded error implies unbounded error, since 2/3 > 1/2 and 1/3 < 1/2.

theorem Complexity.BPP_subset_PP : BPP ⊆ PP

BPP ⊆ PP.

theorem Complexity.P_compl {L : Language} (h : L ∈ P) : Lᶜ ∈ P

P is closed under complement: if L ∈ P then Lᶜ ∈ P.

theorem Complexity.DSPACE_subset_NSPACE (S : ℕ → ℕ) : DSPACE S ⊆ NSPACE S

DSPACE ⊆ NSPACE: every language decidable by a DTM in space O(S) is also decidable by an NTM in space O(S), via the TM.toNTM embedding.

theorem Complexity.NSPACE_mono {S₁ S₂ : ℕ → ℕ} (h : BigO S₁ S₂) : NSPACE S₁ ⊆ NSPACE S₂

NSPACE is monotone: if S₁ =O S₂, then NSPACE S₁ ⊆ NSPACE S₂.

theorem Complexity.L_subset_NL : L ⊆ NL

L ⊆ NL: every deterministic log-space transducer language is also in NL.

theorem Complexity.ZPP_subset_RP : ZPP ⊆ RP

ZPP ⊆ RP: zero-error probabilistic ⊆ one-sided error.

theorem Complexity.ZPP_subset_coRP : ZPP ⊆ coRP

ZPP ⊆ coRP.

theorem Complexity.DTIME_subset_NSPACE (T : ℕ → ℕ) : DTIME T ⊆ NSPACE T

DTIME ⊆ NSPACE (composition of DTIME ⊆ DSPACE and DSPACE ⊆ NSPACE).

theorem Complexity.P_subset_NPSPACE : P ⊆ NPSPACE

P ⊆ NPSPACE via P ⊆ PSPACE ⊆ NPSPACE.

theorem Complexity.P_subset_NEXP : P ⊆ NEXP

P ⊆ NEXP via P ⊆ EXP ⊆ NEXP.

theorem Complexity.P_subset_PP : P ⊆ PP

P ⊆ PP via P ⊆ BPP ⊆ PP.

theorem Complexity.P_union {L₁ L₂ : Language} (h₁ : L₁ ∈ P) (h₂ : L₂ ∈ P) : L₁ ∪ L₂ ∈ P

P is closed under union: derived from DTIME_union and polynomial-bound composition.

theorem Complexity.P_inter {L₁ L₂ : Language} (h₁ : L₁ ∈ P) (h₂ : L₂ ∈ P) : L₁ ∩ L₂ ∈ P

P is closed under intersection: via L₁ ∩ L₂ = (L₁ᶜ ∪ L₂ᶜ)ᶜ.