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?

  • $\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$ Oct 21 '19 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$ Oct 21 '19 at 7:42
  • $\begingroup$ However I think it is not corresponds to alternating machines... $\endgroup$ Oct 21 '19 at 7:48
  • $\begingroup$ Aha, so the machine is allowed to read from z and y simultaneously? $\endgroup$ Oct 21 '19 at 7:50
  • $\begingroup$ @Kristoffer Arnsfelt Hansen Exactly! $\endgroup$ Oct 21 '19 at 8:03

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.


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.