# On complexity class $\mathsf{\Pi_2 L}$

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?

• Why is the unary $\Sigma_2-\text{SUBSETSUM}$ problem in the class? For me it seems impossible to obey the read-once requirement. – Kristoffer Arnsfelt Hansen Oct 21 '19 at 7:38
• @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. – Alexey Milovanov Oct 21 '19 at 7:42
• However I think it is not corresponds to alternating machines... – Alexey Milovanov Oct 21 '19 at 7:48
• Aha, so the machine is allowed to read from z and y simultaneously? – Kristoffer Arnsfelt Hansen Oct 21 '19 at 7:50
• @Kristoffer Arnsfelt Hansen Exactly! – Alexey Milovanov 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.