5
$\begingroup$

I know that when an NL Turing machine is allowed to go back and forth freely, the resulting class of problems solvable on it is NP.

But limit of two passes over the witness tape, does not seem to add much power to the NL machine, if at all.

I am stuck on this problem. What is the resulting complexity class? Is it still NL? How do I prove this?

$\endgroup$
5
  • $\begingroup$ What exactly is an NL Turing machine? $\endgroup$ Nov 22 '16 at 9:04
  • 3
    $\begingroup$ @skankhunt42 It's a Turing machine which cannot modify its input tape, has no output tape, uses $O(\log n)$ space on the worktape, and has "one-way" access to a witness tape (or guess tape). The question is what happens if the machine has access to past guesses. $\endgroup$ Nov 22 '16 at 10:03
  • 2
    $\begingroup$ @skankhunt42 NL = non-deterministic logarithmic-space [en.wikipedia.org/wiki/NL_(complexity)] $\endgroup$
    – Kai
    Nov 22 '16 at 10:05
  • $\begingroup$ @YuvalFilmus I'm assuming that it's a deterministic machine. So does the witness tape correspond to the accepting computational path of the corresponding non-deterministic Turing machine for the NL language and the deterministic machine just verifies whether it is correct? $\endgroup$ Nov 22 '16 at 13:04
  • 1
    $\begingroup$ That's right. The witness tape specifies the nondeterminism. $\endgroup$ Nov 22 '16 at 13:06
3
$\begingroup$

Any finite number of passes will still give you NL. Here is why two passes give you NL — the general case is very similar. You can guess the state of the work tape after the first pass and them simulate the two passes in parallel. In the end you verify that the state of the work tape after the first pass in indeed what you guessed earlier.

$\endgroup$
7
  • 1
    $\begingroup$ Does that extend to the case in which the passes are in different directions? ​ ​ $\endgroup$
    – user12859
    Nov 22 '16 at 14:55
  • $\begingroup$ I think so. You'll just have to go backwards in time, guessing and verifying a preimage at each step. $\endgroup$ Nov 22 '16 at 14:56
  • $\begingroup$ Since the passes for the case I mentioned will get the witness-bits in different orders, I don't see how one can ensure that they are operating on the same witness. ​ ​ $\endgroup$
    – user12859
    Nov 22 '16 at 14:59
  • 1
    $\begingroup$ You will run two simulations in parallel, one forward in time and the other backward in time. $\endgroup$ Nov 22 '16 at 15:00
  • $\begingroup$ Ah, now I get it. ​ That works. ​ ​ ​ ​ $\endgroup$
    – user12859
    Nov 22 '16 at 15:01

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.