Loading ...
Sorry, an error occurred while loading the content.

[Computational Complexity] Extreme Oracles

Expand Messages
  • Lance
    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
    Message 1 of 1 , Aug 15, 2005
    • 0 Attachment
      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)
        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.
      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.

      --
      Posted by Lance to Computational Complexity at 8/15/2005 02:24:00 PM
    Your message has been successfully submitted and would be delivered to recipients shortly.