Skip to main content
MathOverflow

Return to Answer

added 25 characters in body
Source Link
Richard Dore
Richard Dore
  • 5.3k
  • 6
  • 36
  • 43

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

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

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.

Source Link
Richard Dore
Richard Dore
  • 5.3k
  • 6
  • 36
  • 43

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