World's most popular travel blog for travel bloggers.

Resulting complexity class for allowing two passes over witness in NL?

, , No Comments
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.

Best Answer from StackOverflow

Question Source :

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback