Where does the game-theoretic characterization of PH come from?

Question

I have read in a few places that $\mathbf{PH}$ can be interpreted in terms of the complexity of determining the winner in two-player games. I would like to know a) the original reference for this result and/or b) a concise explanation of it that requires little to no background in complexity theory (e.g., less than Goldreich's book).

Answer 1

The answer to part (a) of your question is this reference:

A. Meyer and L. Stockmeyer. The equivalence problem for regular expressions with squaring requires exponential space. In Proceedings of the 13th IEEE Symposium on Switching and Automata Theory, pages 125-129, 1972. [pdf]

What an amazing paper this was! Two later papers that discuss refinements of the result include these:

C. Wrathall. Complete sets and the polynomial-time hierarchy. Theoretical Computer Science 3:23-33, 1977.

A. Chandra, D. Kozen, and L. Stockmeyer. Alternation. Journal of the ACM 28(1):114-133, 1981.

Answer 2

Whenever you have quantifier alternation, you can think of it as a sort of game: one player picks what happens at each universal quantifier, and the other player picks the values at each existential quantifier. The existential player wins if the inner formula at the end is true, the universal player wins if it is false. The whole formula will be true exactly when the existential player has a winning strategy.

Different complexity classes correspond to different types of formulas. For example, any language in NP can be represented as the strings y so the $\exists x. \phi(x,y)$, where the length of $x$ is polynomial in the length of $y$ and $\phi$ can be computed in polynomial time. So NP corresponds to the games where the existential player can make a move that wins immediately. Working up the polynomial hierarchy, you get games (determined by the input) where the existential player always wins in 2 moves, 3 moves, etc., (where each move still has to be polynomial in size). And a language in the whole polynomial hierarchy is the collection of games where there is some fixed n, so that the game is always won by the existential player in n moves. In contrast, PSPACE is the games where the number of move can vary as long as it is polynomial in the length of y. (And the different formulas have to arise in some reasonably uniform way). This is how I usually understand why PH is contained in PSPACE, but then, I am a logician.

Answer 3

I'll take a shot at explaining this. The canonical problem in PH is a problem of this sort: $\exists x_1 \forall x_2 \ldots \exists x_k f(x_1,x_2,\ldots,x_k)$. (The last quantifier is exists or forall depending on whether k is odd or even. Let's take it to be exists for this example.)

The idea is to imagine two players, lets call them Eve (Player 1) and Adam (Player 2). (The names Eve and Adam were chosen so that Eve corresponds to the exists operator, and Adam corresponds to the forAll operator.)

Imagine that $x_1,x_3,\ldots$ describe Eve's moves in this two player game, and $x_2,x_4,\ldots$ describe Adam's moves. The function $f(x_1,x_2,\ldots,x_k)$ evaluates if these moves lead to a win for Eve ($f=1$) or a loss ($f=0$). There is no possibility of a draw.

Now the idea is simple. The value of the boolean expression $\exists x_1 \forall x_2 \ldots \exists x_k f(x_1,x_2,\ldots,x_k)$ exactly tells us if Eve has a winning strategy or not. In words, the boolean expression says this: "Is there a first move ($x_1$) that Eve can play so that no matter what Adam plays in his second move ($x_2$), there exists a move for Eve ($x_3$), so that no matter what Adam plays ........ there exists a $k^{th}$ move for Eve ($x_k$) so that she wins (i.e., $f(x_1,x_2,\ldots,x_k) = 1$)."

So the Boolean expression exactly expresses whether Eve has a winning strategy in this two player game.