Along the way we needed:
- NP in BPP⊕P (follows from Valiant-Vazirani discussed last class)
- ⊕P⊕P = ⊕P (Papadimitrious Zachos)
- NP in BPP implies PH in BPP (Assignment 3)
Links
- PP is as Hard as the Polynomial-Time Hierarchy by Seinsuke Toda
- A Simple Proof of Toda's Theorem by Lance Fortnow
- Two remarks on the power of counting by Christos Papadimitriou and Stathis Zachos
