Three Bizarre Inclusions >NEXP is contained in NPRK( for every U) PSPACE is contained in PRK(for every U) BPP is contained in Pttk(for every U) The decidable sets that are in P Rk for every U are in PSPACE. [AFG111 [CELM] The sets that are in P Rk for every U are decidable Eric Allender. The Strange Link between Incompressibility and Complexity <16>R
Eric Allender: The Strange Link between Incompressibility and Complexity < 16 > Three Bizarre Inclusions NEXP is contained in NPRK (for every U). – The decidable sets that are in NPRK for every U are in EXPSPACE. [AFG11] PSPACE is contained in PRK (for every U). BPP is contained in Ptt RK (for every U). – The decidable sets that are in Ptt RK for every U are in PSPACE. [AFG11] – [CELM] The sets that are in Ptt RK for every U are decidable
Three Bizarre Inclusions >NEXP is contained in NPRK( for every U) PSPACE is contained in PRK(for every U) BPP is contained in Pttk(for every U) The sets that are in Pt k for every U are in PSPACE. [AFG11 Eric Allender. The Strange Link between Incompressibility and Complexity 17>Rr
Eric Allender: The Strange Link between Incompressibility and Complexity < 17 > Three Bizarre Inclusions NEXP is contained in NPRK (for every U). – The decidable sets that are in NPRK for every U are in EXPSPACE. [AFG11] PSPACE is contained in PRK (for every U). BPP is contained in Ptt RK (for every U). – The sets that are in Ptt RK for every U are in PSPACE. [AFG11]
Three Bizarre Inclusions NEXP is contained in NPRK (for every U The sets that are in NPRK for every U are in EXPSPACE. [AFG11 PSPACE is contained in PRK(for every U) BPP is contained in Pttk(for every U) The sets that are in Pt k for every U are in PSPACE. [AFG11 Eric Allender. The Strange Link between Incompressibility and Complexity
Eric Allender: The Strange Link between Incompressibility and Complexity < 18 > Three Bizarre Inclusions NEXP is contained in NPRK (for every U). – The sets that are in NPRK for every U are in EXPSPACE. [AFG11] PSPACE is contained in PRK (for every U). BPP is contained in Ptt RK (for every U). – The sets that are in Ptt RK for every U are in PSPACE. [AFG11]
Three Bizarre Inclusions NEXP is contained in NPRK (for every U The sets that are in NPRK for every U are in EXPSPACE. [AFG11 Conjecture: This should hold for Rc, too BPP is contained in Pttk(for every U) The sets that are in Pt k for every U are in PSPACE. [AFG11 Eric Allender. The Strange Link between Incompressibility and Complexity
Eric Allender: The Strange Link between Incompressibility and Complexity < 19 > Three Bizarre Inclusions NEXP is contained in NPRK (for every U). – The sets that are in NPRK for every U are in EXPSPACE. [AFG11] Conjecture: This should hold for RC, too. BPP is contained in Ptt RK (for every U). – The sets that are in Ptt RK for every U are in PSPACE. [AFG11]
Three Bizarre Inclusions NEXP is contained in NPRK (for every U The sets that are in NPRK for every U are in EXPSPACE. [AFG11 This holds even for sets in eXp rk for all U! BPP is contained in Pttk(for every U) The sets that are in Pt k for every U are in PSPACE. [AFG11 Eric Allender. The Strange Link between Incompressibility and Complexity <20>R
Eric Allender: The Strange Link between Incompressibility and Complexity < 20 > Three Bizarre Inclusions NEXP is contained in NPRK (for every U). – The sets that are in NPRK for every U are in EXPSPACE. [AFG11] This holds even for sets in EXPtt RK for all U! BPP is contained in Ptt RK (for every U). – The sets that are in Ptt RK for every U are in PSPACE. [AFG11]