3
$\begingroup$

For the definition of polynomial hierarchy:

$x \in L \Leftrightarrow \exists u_1 \in \{0, 1\}^{q(|x|)}\forall u_2 \in \{0, 1\}^{q(|x|)} \cdots Q_i u_i \in \{0, 1\}^{q(|x|)} M(x, u_1, \ldots, u_i) = 1$

What does the notation of $M(x, u_1, \ldots, u_i)$ mean? The definition used for $\mathcal{NP}$ is $M(x, \alpha)$ where $\alpha$ is the certificate. What is the intuition for what the $u_i$ signify in terms of the TM $M$?

$\endgroup$

1 Answer 1

3
$\begingroup$

The notation $M(x,u_1,\ldots,u_i)$ stands for a polytime Turing machine with $i+1$ inputs, applied to the inputs $x,u_1,\ldots,u_i$. There are many ways of implementing Turing machines with several different inputs, and from this perspective they are all equivalent, so pick one. (Some examples: several input tapes, inputs separated by special separator symbol, oracle mechanism for obtaining $j$th input.)

Your definition is for languages in $\Sigma_i^P$. When $i = 1$, you get $\mathsf{NP}$. A language $L$ is in $\mathsf{NP}$ is we can verify that $x \in L$ using a polytime Turing machine given a polysize hint $\alpha$. If the verifier is $M$, then this means that $$ x \in L \Leftrightarrow \exists \alpha \in \{0,1\}^{q(|x|)} M(x,\alpha) = 1, $$ where $q$ is a polynomial bounding the size of the witness.

For $i > 1$ there are more quantifier alternations, and you can think of it as a game between two players: the existential player is trying to prove that $x \in L$, while the universal player is trying to prove that $x \notin L$. The game proceeds in $i$ rounds, in which the players alternate giving polysize "witnesses" $u_1,\ldots,u_i$. After $i$ rounds, a judge $M$ is shown the transcript, and makes a verdict; $M(x,u_1,\ldots,u_i)=1$ means that the judge thinks that $x \in L$. A winning strategy for either player is a strategy that guarantees that the verdict will be favorable to them. A language is in $\Sigma_i^P$ if there exists such a polytime judge $M$ such that if $x \in L$ then the existential player has a winning strategy, while if $x \notin L$ then the universal player has a winning strategy.

Here are two examples:

  1. $SAT \in \Sigma_1^P$. In this case the judge $M$ takes as input a formula $x$ and a witness $w$, and checks that $w$ is a satisfying assignment for $x$. If $x \in SAT$ then there is a satisfying assignment, and so the existential player can guarantee that the judge declares $x \in SAT$. If there is no satisfying assignment then the universal player (who is silent) can guarantee that the judge declares $x \notin SAT$.

  2. Circuit minimization $CMIN \in \Sigma_2^P$: a pair $(A,k)$ is in $CMIN$ if $A$ is a circuit encoding a function $f$ which can be computed by a circuit of size at most $k$. The judge $M$ takes as input the pair $(A,k)$, a witness $B$ from the existential player, and a witness $x$ from the universal player, and accepts if $B$ is a circuit of size at most $k$ that agrees with $A$ on the input $x$. If $(A,k) \in CMIN$ then the winning strategy of the existential player is to produce a circuit $B$ of size at most $k$. If $(A,k) \notin CMIN$ then the winning strategy of the universal player is, for each circuit $B$ of size at most $k$, to find an input $x$ on which $A$ and $B$ disagree.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.