MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Hi, How to prove that the two definitions of the complexity class NL are equivalent. 1st definition is with a non deterministic logspace TM, and the second is with a deterministic logspace verifier who uses a readonce witness tape?

Where does the proof fail if the verifier can go backwards on the witness tape?


share|cite|improve this question

You can suppose that every non-deterministic choice is given on the witness tape, I think it is easy to see that these definitions are the same, if you have further doubts, then please specify exactly where. The proof fails if the witness tape is not one-way because an NL machine cannot remember what choices it made earlier, while with a two-way witness tape you could scroll back and check.

share|cite|improve this answer

As domotorp already wrote, the equivalence is easy: on the one hand, a deterministic verifier can simulate and check the computation if given the sequence of nondeterministic choices made by the NL algorithm on the witness tape, on the other hand, a nondeterministic logspace machine can simulate the verifier while replacing the witness tape with nondeterministic guesses.

If the verifier has unrestricted access to the witness tape, the class you get is all of NP. On the one hand, the logspace verifier is in particular polynomial-time. On the other hand, given a nondeterministic poly-time machine, one can use the transcript of its accepting run as a witness, and one can check the correctness of the transcript by a logspace algorithm.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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