Polynomial Hierarchy --- polynomial time TM

Question

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

Answer 1

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)|$).

• zpavlinovic: 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.
• Yuval Filmus: You're right, I haven't noticed the polynomial bounds. But they should be part of the formula.
• Yuval Filmus: 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.