#### Corollary 9.27

*Proof*

## 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 ...

Get *Theory of Computational Complexity, 2nd Edition* now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.