**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}=NP

^{NP}⊆ NP

^{BPP}⊆BPP

^{BPP}=BPP.

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.

## No comments:

## Post a Comment