Question

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?

Thanks

Answer 1

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.

Answer 2

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.