1
$\begingroup$

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

Improve this question
$\endgroup$

2 Answers 2

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
2
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ How do you guess the polynomially long certificate, when the machine has only logspace? $\endgroup$
    – Tony
    Nov 25, 2019 at 19:57
  • $\begingroup$ What do you mean? The logspace machine does not guess the certificate. The certificate is given on the witness tape. $\endgroup$
    – Emil Jeřábek
    Nov 25, 2019 at 20:08
  • $\begingroup$ Referring to: "a nondeterministic logspace machine can simulate the verifier while replacing the witness tape with nondeterministic guesses". Perhaps I am missing something, but should not the machine run out of tape if it tried to make polynomial guesses? $\endgroup$
    – Tony
    Nov 25, 2019 at 20:12
  • 1
    $\begingroup$ Oh, here. I thought you were talking about the second paragraph. The machine is just making guesses on the fly, it does not record them anywhere. $\endgroup$
    – Emil Jeřábek
    Nov 25, 2019 at 21:02
  • $\begingroup$ Thank you for the clarification :-). Are there any sources on how this works in more detail? It would appear the guesses are still polynomially bounded? $\endgroup$
    – Tony
    Nov 25, 2019 at 21:47

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.