5 - The polynomial hierarchy and alternations

Summary

[S]ynthesizing circuits is exceedingly difficulty. It is even more difficult to show that a circuit found in this way is the most economical one to realize a function. The difficulty springs from the large number of essentially different networks available.

– Claude Shannon, 1949

We have already encountered some ways of “capturing” the essence of families of computational problems by showing that they are complete for some natural complexity class. This chapter continues this process by studying another family of natural problems (including one mentioned in Shannon's quote at the begginning of this chapter) whose essence is not captured by nondeterminism alone. The correct complexity class that captures these problems is the polynomial hierarchy, denoted PH, which is a generalization of P, NP and coNP. It consists of an infinite number of subclasses (called levels) each of which is important in its own right. These subclasses are conjectured to be distinct, and this conjecture is a stronger form of P ≠ NP. This conjecture tends to crop up (sometimes unexpectedly) in many complexity theoretic investigations, including in Chapters 6, 7, and 17 of this book.

In this chapter we provide three equivalent definitions of the polynomial hierarchy:

1. In Section 5.2 we define the polynomial hierarchy as the set of languages defined via polynomial-time predicates combined with a constant number of alternating forall (∀) and exists (∃) quantifiers, generalizing the definitions of NP and coNP from Chapter 2.

2. […]