4
$\begingroup$

I suggest the following definition of $\mathsf{\Pi_2 L}$ (similarly to the certificate definition of $\mathsf{NL}$):

A language $L$ belongs to $\mathsf{\Pi_2 L}$ iff there exists a deterministic Turing Machine $M$ and polynomials $p$ and $q$ such that

$$x \in L \Leftrightarrow \forall z \in \{0,1\}^{p(|x|)} \exists y \in \{0,1\}^{q(|x|)} M(x, z, y) =1.$$ Here $x$ is placed on its input tape and $z$ and $y$ are placed on its special read-once tapes, and $M$ uses at most $O(\log |x|)$ space on its read/write tapes for every input $x$. We can read $z$ and $y$ simultaneously.

What can we say about this complexity class? Since $\mathsf{NL} \subseteq \mathsf{P}$ we have $\mathsf{\Pi_2 L} \subseteq \mathsf{coNP}$. Can we say something else about this class? An example of a language from $\mathsf{\Pi_2 L}$ is here: Is unary $\Pi_2$-SUBSETSUM coNP-complete?

$\endgroup$
  • $\begingroup$ Why is the unary $\Sigma_2-\text{SUBSETSUM}$ problem in the class? For me it seems impossible to obey the read-once requirement. $\endgroup$ – Kristoffer Arnsfelt Hansen Oct 21 at 7:38
  • $\begingroup$ @Kristoffer Arnsfelt Hansen at the first tape it is written the subset $S$ and at the second tape it is written subset $H$. Both of them must be given in the same order as the input. So, it is possible to verify that H is subset of S. $\endgroup$ – Alexey Milovanov Oct 21 at 7:42
  • $\begingroup$ However I think it is not corresponds to alternating machines... $\endgroup$ – Alexey Milovanov Oct 21 at 7:48
  • $\begingroup$ Aha, so the machine is allowed to read from z and y simultaneously? $\endgroup$ – Kristoffer Arnsfelt Hansen Oct 21 at 7:50
  • $\begingroup$ @Kristoffer Arnsfelt Hansen Exactly! $\endgroup$ – Alexey Milovanov Oct 21 at 8:03
5
$\begingroup$

If I got this right, $\Pi_2L$ as defined above is equal to co-NP. The co-NP-complete DNF tautology sits in $\Pi_2L$: Use z for the assignment and y to choose which clause to check. To show $\Pi_2L$ in co-NP, universally guess z and the rest can be computed in P.

$\endgroup$

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.