patternMinor
Intuition for PH notation in Arora-Barak's Computational Complexity
Viewed 0 times
aroracomputationalbaraknotationforcomplexityintuition
Problem
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$?
$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$?
Solution
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:
-
$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$.
-
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.
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:
-
$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$.
-
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.
Context
StackExchange Computer Science Q#42934, answer score: 3
Revisions (0)
No revisions yet.