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.
No comments:
Post a Comment