Theory of Computational Complexity, 2nd Edition

Corollary 9.27

1. If , then the polynomial-time hierarchy collapses to BPP and, hence, to .
2. For any k ≥ 1, if , then the polynomial-time hierarchy collapses to .

Proof

Part (a) follows immediately from the above theorem and Corollary 8.33. Part (b) follows from the generalized BPP theorem (Theorem 8.34), which implies that .

9.4 and the Polynomial-Time Hierarchy

In this section, we prove that . From Theorem 9.26, we only need to show that . The main idea is that the number of accepting computations of an NTM can be amplified without changing its parity. Recall that denotes the ...