2
$\begingroup$

Consider, for example, the definition for $\Sigma_2^p$ complexity class.

$$ x \in L \Leftrightarrow \exists u_1 \forall u_2 \;M(x, u_1, u_2) = 1, $$

where $u_1, u_2 \in \{0,1\}^{p(|x|)}$, for some polynomial $p$. Here, $M$ must be polynomial time. But polynomial in the size of what exactly? For example, if we choose (guess) some $u_1$, do I consider it to be fixed size when talking about time complexity of $M$? More precisely, should $M$ be polynomial only in the size of $x$?

An example. Consider the problem whether, given a graph $A$, there exists a graph $B$ such that $B$ is subgraph isomorphic to $A$.

$$A \in L \Leftrightarrow \exists B \; \text{SubGraphIsomorphic}(A, B) = 1 $$

Now, subgraph isomorphism is NP-complete. If $B$ is fixed, then there is a TM that implements $\text{SubGraphIsomorphic}$ in deterministic polynomial time. If $B$ is not fixed, then I cannot claim such a thing unless I know $\sf P=NP$. Is this problem in $\Sigma_{1}^{p}$, i.e. $\sf NP$? (Ok, this problem has trivial solutions, but I hope it helps to pinpoint my confusion.)

My confusion generalizes for all $\Sigma_{i}^p$.

$\endgroup$
3
$\begingroup$

Your definition of $\Sigma_2^P$ is a bit misleading. Both $u_1$ and $u_2$ have to be bounded in length by some polynomial in $|x|$, and this usually forms part of the formula rather than part of the descriptive text. The predicate $M$ has to be polynomial time in the combined input length, which is the same as being polynomial time in $|x|$ since both $u_1$ and $u_2$ have length polynomial in $|x|$.

You have not described the predicate SubgraphIsomorphic correctly. You are given two graphs $A,B$, and you have to decide whether $B$ is isomorphic to a subgraph of $A$. We write it as an NP-predicate as follows: $$(A,B) \in \mathrm{SubgraphIsomorphic} \leftrightarrow \exists |P| \leq |(A,B)| \mathrm{Isomorphic}(A,B,P), $$ where $\mathrm{Isomorphic}(A,B,P)$ is true if $P$ encodes an injection from the vertex set of $B$ to the vertex set of $A$, and $(x,y)$ is an edge of $B$ iff $(P(x),P(y))$ is an edge of $A$. This is a polytime predicate. Moreover, the injection can be coded in length polynomial in the input $(A,B)$ (for simplicity, I'm assuming that the encoding is such that $|P| \leq |(A,B)|$).

$\endgroup$
  • $\begingroup$ 1) I believe I mention the bounds for $u_1$ and $u_2.$ 2) Your problem seems to be different than mine. My problem has trivial solutions, but I have introduced it just to explain the parts that are confusing me. $\endgroup$ – bellpeace Mar 29 '14 at 3:00
  • $\begingroup$ You're right, I haven't noticed the polynomial bounds. But they should be part of the formula. $\endgroup$ – Yuval Filmus Mar 29 '14 at 3:04
  • 1
    $\begingroup$ Regarding your SubGraphIsomorphic, as you mention SubGraphIsomorphic is in NP and so can be written in the form I give in my answer. You can then fold both $\exists$ quantifiers to see that your SubGraphIsomorphic is also in NP. $\endgroup$ – Yuval Filmus Mar 29 '14 at 3:05

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.