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.


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$ Jul 26 '17 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$
    – omrib40
    Jun 26 at 16:09
  • $\begingroup$ Nondeterministic computation has a verification interpretation, and also a guessing interpretation. $\endgroup$ Jun 26 at 16:11

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.