While trying to understand the concept of polynomial hierarchy, I noticed that there are several ways to define it. And the most confusing thing about the situation is to see the equivalence between those definitions intuitively. What I want to know for now is the relation between oracle machines and existential/universal quantifiers from the viewpoint of polynomial hierarchy.

By Wiki, the polynomial hierarchy is the generalization of the classes P, NP, and co-NP to oracle machines. The addition of oracles (not sure this is a suitable expression) results in the increase of the hierarchy.

On the other hand, another way to define the polynomial hierarchy is to use the quantifiers $\forall$ and $\exists$. According to this lecture note (http://www.cs.cornell.edu/courses/cs6810/2009sp/scribe/lecture5.pdf), a language $L$ is in $\Sigma_i$ iff $\exists$ a polynomial time relation $R$ s.t. $x\in L$ iff \begin{equation} \exists y_1\forall y_2\cdots Q_iy_iR(x,y_1,\cdots y_i), \end{equation} where $Q_j=\forall$ if $j$ is even and $Q_j=\exists$ if $j$ is odd. And $L$ is in $\Pi_i$ iff its complementary $\bar{L}$ is in $\Sigma_i$.

From the above definitions, it seems that there exist a sort of one-to-one correspondence between the inclusion of oracle and the addition of quantifiers.

Can anyone help me understand how the oracles in a Turing machine plays the role of quantifiers in predicates?


The oracles do not play the role of quantifiers, they play the role of everything but the first quantifiers.

First, observe how NP relates to $\exists yR(x,y)$ with $R$ in P. That means that NP allows existential nondeterminism followed by computation in P.

Similarly, $\Pi_1$ "is" $\forall yR(x,y)$ with $R$ in P. Now for $\Sigma_2$ we have the same with an additional $\exists$ at the front: $\exists y_1\forall y_2R(x,y_1,y_2)$ with $R$ in P. Or, in other words, $\exists y_1 R'(x,y_1)$ with $R'$ in $\Pi_1$. So we have existential nondeterminism followed by computation in $\Pi_1$. And that is more or less the same as NP with a $\Pi_1$ oracle.

In general, the first quantifier specifies whether we are in the existential or universal case. The rest of the formula then describes a lower level of the hierarchy which we use as an oracle.

| cite | improve this answer | |
  • $\begingroup$ Thank you for the answer. So the oracle is not directly related to the concept of quantifiers themselves. It seems that I understand better now about how the increase of quantifiers is realized with oralcles. $\endgroup$ – sbthesy Mar 23 '18 at 2:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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