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

[My Computational Complexity Web Log] When Good Theorems Have Bad Proofs

Expand Messages
  • Lance Fortnow
    Here is one of my favorite examples of a bad proof for what turns out to be a correct theorem. Theorem: If NP is in BPP then the whole polynomial-time
    Message 1 of 1 , Oct 24, 2003
    • 0 Attachment
      Here is one of my favorite examples of a bad proof for what turns out to be a correct theorem.

      Theorem: If NP is in BPP then the whole polynomial-time hierarchy is in BPP.

      Let's focus on simply showing Σ2 is in BPP if NP is in BPP. The rest is straightforward induction. Here is our first proof:

      Σ2=NPNP⊆ NPBPP⊆BPPBPP=BPP.
      Do you see the problem with this proof?

      To get a correct proof (first due to Zachos) we need to use Arthur Merlin games. Consider a Σ2 language L as an ∃∀ expression. Since NP is in BPP, we can replace the ∀ with a probabilistic test. This gives us what is known as MA or a Merlin-Arthur game where the powerful Merlin sends a message that Arthur can probabilistically verify. A now classic result shows that MA is contained in AM, where Arthur provides a random string to Merlin who must then provide a proof based on that string. Once again we apply the NP in BPP assumption to allow Arthur to simulate Merlin probabilistically and now we have a BPP algorithm for L.

      The problem in the first proof is in the second "⊆". The assumption NP in BPP does not imply NPA in BPPA for all A.

      --
      Posted by Lance Fortnow to My Computational Complexity Web Log at 10/24/2003 08:59:53 AM

      Powered by Blogger Pro

    Your message has been successfully submitted and would be delivered to recipients shortly.