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.
  • 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.
You can replace ⊕P with ModkP for any prime k in any of the above. We don't believe any of the statements to be true in the "real world" but all of them remain open and would require nonrelativizing techniques to disprove.
at

10 comments:

  1. Anonymous11:26 AM, August 16, 2005

    Is there a good resource for learning what these oracles are? Or at least pointers to the right papers?

    ReplyDelete
  2. Lance Fortnow1:49 PM, August 16, 2005

    I added links the the main papers.

    ReplyDelete
  3. Anonymous10:24 PM, August 16, 2005

    In one of your previous posts you mentioned that what you like about TCS is that what we now know will remain true for ever.

    How 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.

    ReplyDelete
  4. Lance Fortnow7:20 AM, August 17, 2005

    If nonrelativizing proofs were so easy, why are these problems still open?

    Check out my survey, The Role of Relativization in Complexity Theory.

    ReplyDelete
  5. Anonymous10:45 AM, August 17, 2005

    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.

    ReplyDelete
  6. Anonymous5:23 PM, August 17, 2005

    I 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.

    I 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.

    ReplyDelete
  7. Anonymous1:56 PM, August 20, 2005

    Having now skimmed Lance's paper above, I would like to change my entry to question for Lance.

    The 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?

    ReplyDelete
  8. Anonymous10:26 PM, September 11, 2017

    I thought the Buhrman-Fenner-Fortnow-Torenvliet paper shows P^NP = NEXP. How do you get P^RP = NEXP?

    ReplyDelete
    Replies
    1. Lance Fortnow8:44 AM, September 12, 2017

      Not 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.

      Delete
  9. Anonymous12:15 PM, April 11, 2024

    Is there an oracle which outs $PP\in\oplus P$ but $NEXP\not\subseteq EXP$?

    ReplyDelete