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}[1]$.

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

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

It is clear that $\mathsf{NL}\subseteq \mathsf{NL}[2]$. For the second part I tried to construct a verifier that can read the witness only once for $L\in \mathsf{NL}[2]$. I said that the verifier expects a witness of the form $w\sharp w$ and runs the $\mathsf{NL}[2]$ 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.


1 Answer 1


You can show that $\mathsf{NL}[2] \subseteq \mathsf{NL}$ as follows. We are given an $\mathsf{NL}[2]$ 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}$.

  • $\begingroup$ Wow this is brilliant thank u very much!!!!! $\endgroup$ Commented Jul 26, 2017 at 14:58
  • $\begingroup$ @Yuval Filmus I couldn't fully understand the solution you suggest. especialy "The first that M does is to guess the state sigma of M'" how can M guess a state? according to the definition is a deterministic verifier, isnt it? and why is it guessing a state of M' how this helps us? furthermore, where is the witness held on? on M witness tape? $\endgroup$
    – BOB123
    Commented Jun 26, 2021 at 16:09
  • $\begingroup$ Nondeterministic computation has a verification interpretation, and also a guessing interpretation. $\endgroup$ Commented Jun 26, 2021 at 16:11
  • $\begingroup$ 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). $\endgroup$
    – Dennis
    Commented Nov 23, 2021 at 7:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.