- 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$?
ReplyDeleteIs there an oracle giving $NP=RP\neq coNP=coRP$ and $PP=BPP=AM=coAM=MA$ implying collapse of non-determinstic and conon-deterministic classes with probabilistic verifiers does not force the collapse with deterministic verifiers or do we at least know $AM=coAM=PP=BPP$ forces $NP=coNP$?
ReplyDeleteLet's consider the oracle where BPP = EXP^NP. This implies BPP= PP= AM = co-AM. Also you can't have NP = co-NP since that would imply NP = Sigma_2 and we know BPP is not equal to EXP^Sigma_2.
DeleteVery strange. But if $BPP\subseteq QuasiP\not\subseteq P\poly$ (maybe explicitly and stringky $DTIME[2^{O(\log^{100}n)}]\not\subseteq P\poly$) can be shown (which means $E$ needs a superpoly circuit) then at least then would $AM=coAM=PP=BPP$ force $NP=coNP$ or even for this type of collapss we need full or almost full power of $E$ requires fully exponential circuits?
DeleteI'd be surprised if you could get NP=co-NP from those assumptions. I suspect an oracle is possible, but it would require some trickier combinatorics.
DeleteVery surprising. We can assume we can dequantize QMA=coQMA to AM=coAM but still we cannot derandomize to NP=coNP. So dequantization is an inherently easier process than derandomization. Perhaps that would explain why there are no lower bound implications of BPP=BQP like there is for P=BPP. In this sense BQP is closer to BPP which also explains why it is very hard to get any derandomization results at all.
ReplyDelete