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

[Computational Complexity] Making Pigs Fly

Expand Messages
  • Lance
    Toda s famous theorem states that the polynomial-time hierarchy reduces to counting problems (in complexity terms PH P #P ). His proof uses two lemmas: PHBPP P
    Message 1 of 1 , Jun 3 4:42 AM
    • 0 Attachment
      Toda's famous theorem states that the polynomial-time hierarchy reduces to counting problems (in complexity terms PH ⊆ P#P). His proof uses two lemmas:
      • PH⊆BPP⊕P
      • BPP⊕P⊆P#P
      Here is a straightforward proof of the first lemma using relativizable versions of previously known results.
      1. ⊕P⊕P=⊕P (Papadimitriou-Zachos)
      2. NP⊆BPP implies PH⊆BPP (Zachos and also here)
      3. NP⊆BPP⊕P (follows easily from Valiant-Vazirani)
      4. NP⊕P⊆BPP⊕P⊕P (relativize 3 to ⊕P)
      5. NP⊕P⊆BPP⊕P (apply 1)
      6. NP⊕P⊆BPP⊕P implies PH⊕P⊆BPP⊕P (relativize 2 to ⊕P)
      7. PH⊕P⊆BPP⊕P (use 5 and 6)
      8. PH⊆BPP⊕P (immediate corollary of 7)
      We often call results like Zachos (2 above) a "pigs can fly" theorem because we don't believe the assumption in this case that NP is in BPP. This proof shows that relativization can give pigs wings and lead to some interesting containments.

      --
      Posted by Lance to Computational Complexity at 6/3/2005 06:29:00 AM
    Your message has been successfully submitted and would be delivered to recipients shortly.