**Problem Detail:**

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?

###### Asked By : AmirB

###### Answered By : Yuval Filmus

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.

Question Source : http://cs.stackexchange.com/questions/66306

**3200 people like this**

## 0 comments:

## Post a Comment

Let us know your responses and feedback