About $ \Sigma_2^p$

Does $ \Sigma_2^p$ have a complete problem?

$ L = \{x\mid \exists y_1 \forall y_2 M(x, y_1, y_2)\} \in \Sigma_2^p$

All the machines we have been using are Deterministic Machine.

Alternating Turing Machine For $ \mathsf{HAMCIRCUIT}$


\begin{algorithmic}
\STATE Read $G = (V, E)$
\FOR{each edge $e \in E$}
\STATE...
...Don't
\ENDFOR
\STATE Accept if $C$ is a Hamiltonic Circuit.
\end{algorithmic}



bighead 2008-10-29