KC and randomness ) When it makes no difference, We'l write“R” instead of r or r >Basic facts R is undecidable but it is not "easy to use it as an oracle R is not NP-hard under poly-time sm reductions, unless P=NP Things get more interesting when we consider more powerful types of reducibility Eric Allender. The Strange Link between Incompressibility and Complexity <11>R
Eric Allender: The Strange Link between Incompressibility and Complexity < 11 > K, C, and Randomness When it makes no difference, we’ll write “R” instead of RC or RK. Basic facts: – R is undecidable – …but it is not “easy” to use it as an oracle. – R is not NP-hard under poly-time ≤m reductions, unless P=NP. – Things get more interesting when we consider more powerful types of reducibility
Three Bizarre Inclusions NEXP is contained in NPR. [ABK06 PSPACE is contained in PR [ABKMR06 BPP is contained in (A: A is poly-time s r [BFKL101 Astt reduction is a non-adaptive reduction On input X, a list of queries is formulated before receiving any answer from the oracle Eric Allender. The Strange Link between Incompressibility and Complexity 12
Eric Allender: The Strange Link between Incompressibility and Complexity < 12 > Three Bizarre Inclusions NEXP is contained in NPR. [ABK06] PSPACE is contained in PR. [ABKMR06] BPP is contained in {A : A is poly-time ≤tt R}. [BFKL10] – A ≤tt reduction is a “non-adaptive” reduction. – On input x, a list of queries is formulated before receiving any answer from the oracle
Three Bizarre Inclusions NEXP is contained in NPR. [ABK06 PSPACE is contained in PR [ABKMRO6 BPP is contained in Pt. [BFKL10 Bizarre, because a non-computable upper bound is presented on complexity classes We have been unable to squeeze larger complexity classes inside. Are these containments optimal? Eric Allender. The Strange Link between Incompressibility and Complexity
Eric Allender: The Strange Link between Incompressibility and Complexity < 13 > Three Bizarre Inclusions NEXP is contained in NPR. [ABK06] PSPACE is contained in PR. [ABKMR06] BPP is contained in Ptt R. [BFKL10] “Bizarre”, because a non-computable “upper bound” is presented on complexity classes! We have been unable to squeeze larger complexity classes inside. Are these containments optimal?
Three Bizarre Inclusions NEXP is contained in NPR. [ABK06 PSPACE is contained in PR [ABKMRO6 BPP is contained in Pt. [BFKL10 Bizarre, because a non-computable upper bound is presented on complexity classes If we restrict attention to Ru then we can do better Eric Allender. The Strange Link between Incompressibility and Complexity 14>R
Eric Allender: The Strange Link between Incompressibility and Complexity < 14 > Three Bizarre Inclusions NEXP is contained in NPR. [ABK06] PSPACE is contained in PR. [ABKMR06] BPP is contained in Ptt R. [BFKL10] “Bizarre”, because a non-computable “upper bound” is presented on complexity classes! If we restrict attention to RK , then we can do better…
Three Bizarre Inclusions NEXP is contained in NPrK PSPACE is contained in PRK BPP is contained in PRK Eric Allender. The Strange Link between Incompressibility and Complexity
Eric Allender: The Strange Link between Incompressibility and Complexity < 15 > Three Bizarre Inclusions NEXP is contained in NPRK. – The decidable sets that are in NPRK for every U are in EXPSPACE. [AFG11] PSPACE is contained in PRK. BPP is contained in Ptt RK. – The decidable sets that are in Ptt RK for every U are in PSPACE. [AFG11]