- 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 [Corollary 4.8])
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
Extreme Oracles
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.
Subscribe to:
Post Comments (Atom)
Is there a good resource for learning what these oracles are? Or at least pointers to the right papers?
ReplyDeleteI added links the the main papers.
ReplyDeleteIn one of your previous posts you mentioned that what you like about TCS is that what we now know will remain true for ever.
ReplyDeleteHow do you feel about these oracle results, especially when considering the IP vs. PSPACE affair? I would think that this should have ended this way of studying complexity classes
as it means that these results essentially don't say anything.
If nonrelativizing proofs were so easy, why are these problems still open?
ReplyDeleteCheck out my survey, The Role of Relativization in Complexity Theory.
Wow, Lance, I don't think he was claiming they were easy. He was asking how much insight they bring into the unrelativized question. I think there is general agreement that this line of attack turned out to be not as fruitful as it was originally hoped.
ReplyDeleteI think that it is an important judgement call as to whether any given oracle is realistic, i.e., that you could hope to imitate it with a language in P or BPP. One famous old construction is that P^PSPACE = NP^PSPACE. But as evidence that P = NP, this is circular: if you believe that PSPACE is a realistic oracle, then you believe a lot more than P = NP.
ReplyDeleteI think that it was a reasonable hope that random oracles are realistic. Because, to appearances, featureless junk output can be generated in polynmomial time. Despite the result that IP = PSPACE, you could still make a case for realism of random oracles (at least to a bystander like me), because the realism of IP and PSPACE is debatable. (Okay, IP and PSPACE aren't directly realistic. But maybe they admit realistic indirect interpretations.)
This is an important issue in quantum computation. Shor's algorithm actually finds the period of an arbitrary periodic function (which is injective within the period). This gives you an immediate oracle separation between BPP and BQP. How realistic is it? Famously, factoring gives you one realistic imitation of an oracular periodic function. You could speculate that factoring is in BPP, which would make it a poor imitation. But there might still be many other possible imitations.
Having now skimmed Lance's paper above, I would like to change my entry to question for Lance.
ReplyDeleteThe paper says, "We however would like to argue that we should never have believed the random oracle hypothesis in the first place." If so, then how should we use oracles to buttress what we believe?
For example, I want to believe that BPP ? BQP. I even want to believe that period-finding (either the Shor or the Simon version) is not in BPP. Should I retreat to a neutral opinion until someone proves that P ? PSPACE? I note that relative to a random oracle, period-finding is not in BPP. Can I interpret this random-oracle result as valid indirect evidence? If not, would some other kind of oracle be better? Or would a collapse result (if BPP = BQP, then some large class = some small class) be better?
I thought the Buhrman-Fenner-Fortnow-Torenvliet paper shows P^NP = NEXP. How do you get P^RP = NEXP?
ReplyDeleteNot sure we ever wrote this up but it is an easy modification. Instead of putting a single z in the oracle (see the construction), put in all eligible z. Then an RP machine can find a z.
DeleteIs there an oracle which outs $PP\in\oplus P$ but $NEXP\not\subseteq EXP$?
ReplyDelete