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

CC BY-SA 4.0
2019-10-21T13:40:09.340Z
2019-10-21T13:40:09.340Z
Lance Fortnow
<p>I suggest the following definition of <span class="math-container">$\mathsf{\Pi_2 L}$</span>  (similarly to the certificate definition of <span class="math-container">$\mathsf{NL}$</span>):</p>

<p>A language <span class="math-container">$L$</span> belongs to <span class="math-container">$\mathsf{\Pi_2 L}$</span> iff there exists a deterministic Turing Machine <span class="math-container">$M$</span> and polynomials <span class="math-container">$p$</span> and <span class="math-container">$q$</span> such that </p>

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

<p>What can we say about this complexity class? Since <span class="math-container">$\mathsf{NL} \subseteq \mathsf{P}$</span> 
we have  <span class="math-container">$\mathsf{\Pi_2 L} \subseteq \mathsf{coNP}$</span>. Can we say something else about this class? An example of a language from <span class="math-container">$\mathsf{\Pi_2 L}$</span> is here: <a href="https://cstheory.stackexchange.com/questions/45545/is-unary-pi-2-subsetsum-conp-complete">Is unary $\Pi_2$-SUBSETSUM coNP-complete?</a> </p>

CC BY-SA 4.0
2019-10-21T07:38:05.193Z
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
CC BY-SA 4.0
2019-10-21T07:42:34.673Z
@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
CC BY-SA 4.0
2019-10-21T07:48:27.337Z
However I think it is not corresponds to alternating machines...
Alexey Milovanov
CC BY-SA 4.0
2019-10-21T07:50:56.697Z
Aha, so the machine is allowed to read from z and y simultaneously?
Kristoffer Arnsfelt Hansen
CC BY-SA 4.0
2019-10-21T08:03:19.293Z
@Kristoffer Arnsfelt Hansen Exactly!
Alexey Milovanov
<cc.complexity-theory><complexity-classes><space-complexity>
On complexity class $\mathsf{\Pi_2 L}$
Alexey Milovanov
# On complexity class $\mathsf{\Pi_2 L}$

(Asked by: username_0 on 2019-10-20)

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?](https://cstheory.stackexchange.com/questions/45545/is-unary-pi-2-subsetsum-conp-complete)

**Tags:** cc.complexity-theory, complexity-classes, space-complexity
> **Comments:**
> **username_1**: Why is the unary $\Sigma_2-\text{SUBSETSUM}$ problem in the class? For me it seems impossible to obey the read-once requirement.  
> **username_0**: @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.  
> **username_0**: However I think it is not corresponds to alternating machines...  
> **username_1**: Aha, so the machine is allowed to read from z and y simultaneously?  
> **username_0**: @Kristoffer Arnsfelt Hansen Exactly!  

---

## 1 answers

### Answer by username_2 on 2019-10-21. Score: 6 | Accepted answer

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.


---

