- P=PSPACE (Baker-Gill-Solovay)
One of the original oracles collapses everything. P=NP=co-NP=PH=⊕P=PP=BQP=P#P=PSPACE=NPSPACE.
- Generic Oracles (Blum-Impagliazzo or see our toolkit paper)
These oracles separate as much as possible. P≠NP, the polynomial-time hierarchy is infinite, PP is not in PNP, NP is not in ⊕P and much more. Oddly enough they diagonalize against machines that need to fulfill a promise condition and so with the appropriate construction one also gets P=NP∩co-NP=UP=BPP=BQP.
- P=⊕P and NP=EXP (Beigel-Buhrman-Fortnow)
Relative to this oracle ZPP=⊕EXP and the isomorphism conjecture holds (all NP-complete problems are reducible to each other via invertible bijections).
- P=NP and ⊕P=EXP (Beigel-Maciel)
The polynomial-time hierarchy collapses to P and yet the exponential hierarchy sits inside ⊕P.
- P=⊕P and BPP=EXPNP (Buhrman-Torenvliet)
No even very weak derandomization for BPP. Valiant-Vazirani puts NP in RP⊕P but in this oracle NP is not even in co-NP⊕P.
- PRP=NEXP (Buhrman-Fenner-Fortnow-Torenvliet)
No even very weak derandomization for RP. Implies PNP=PNEXP (also implied by the next oracle).
- PNP=⊕P=PEXP (Aaronson)
A strong version of Beigel's oracle where PNP is not in PP (though the entire polynomial-time is in PPP) and PP is not closed under Turing-reductions.
Monday, August 15, 2005
Let's look at some relativized worlds which really push the limits of what we don't know how to prove. Once again I refer you to the zoo for definitions of these classes.