# Polynomial Hierarchy — polynomial time TM

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

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)|$).
• 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. – bellpeace Mar 29 '14 at 3:00
• 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. – Yuval Filmus Mar 29 '14 at 3:05