Making Pigs Fly

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.