patternMinor
Resulting complexity class for allowing two passes over witness in NL?
Viewed 0 times
allowingwitnessresultingtwopassesforclassovercomplexity
Problem
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?
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?
Solution
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.
Context
StackExchange Computer Science Q#66306, answer score: 3
Revisions (0)
No revisions yet.