# $\mathsf{NL}$ versus $\mathsf{NL}$

There is an equivalent definition for the class $\mathsf{NL}$ with verifier. Those verifiers are deterministic Turing machines that can read the witness tape only once in one way from left to right.

Given a function $f:\mathbb{N}\to\mathbb{N}$ we say that $\mathsf{NL}[f(n)]$ is the class obtained by the above definition but the verifier can read the witness $f(n)$ times for an input of size $n$ (i.e. when the verifier finished reading the witness the goes straight to the beginning of it).

We can see of course that $\mathsf{NL}=\mathsf{NL}$.

The question is whether $\mathsf{NL}=\mathsf{NL}$.

Clarification: Prove or Disprove that $\mathsf{NL}=\mathsf{NL}$.

It is clear that $\mathsf{NL}\subseteq \mathsf{NL}$. For the second part I tried to construct a verifier that can read the witness only once for $L\in \mathsf{NL}$. I said that the verifier expects a witness of the form $w\sharp w$ and runs the $\mathsf{NL}$ verifier for $L$ with $w$ and then when it finishes and wants to read it again with second copy of $w$. But the major problem with my approach is that maybe someone tricked me and put a non equal sub-witnesses and I won't be able to find out about this with $\log(n)$ space thus it does not work.

You can show that $\mathsf{NL} \subseteq \mathsf{NL}$ as follows. We are given an $\mathsf{NL}$ machine $M$, and we want to simulate it with an $\mathsf{NL}$ machine $M'$. The first that $M$ does is to guess the state $\sigma$ of $M'$ after it finishes reading the witness tape for the first time. It then simulates two copies of $M$, one starting at $M$'s initial state, and the other starting at $\sigma$. After going through the witness tape, it verifies that the first copy has reached $\sigma$, and that the second copy has reached an accepting state.
In this way you can show that $\mathsf{NL}[O(1)] = \mathsf{NL}$.
• I think that what @omrib40 meant is that you provided a nondeterministic log-space TM (which guesses the state $\sigma$), but then you said that it "reads the witness tape" (which is another interpretation of NL, not using NDTM). There might be place for elaboration about how the witness is read. I think you can just keep guessing the witness (in some way, consistently with the two copies). Nov 23, 2021 at 7:21