<p>For any NP language, we usually describe the language as having a polynomial time TM M such that for yes instance x you can find a witness such that M(x, w) accepts and for no instance M will not accept x no matter what the witness is.</p>
<p>I know that nondeterminism refers to transition in a state machine, so technically the witness w is read once only (you shouldn’t be allowed to rewind) but in the case of NP we can bypass this restriction by recording w locally and rewind all we want.</p>
<p>However, for NL it seems like you can’t do shouldn’t be allowed to rewind back to earlier parts of witness w as you can’t simulate the rewinding due to space constraints.</p>
<p>My question is, how is witness w usually modeled in an NL Turing Machine and how would the language be different if we are allowed to rewind witness in such TM?</p>

CC BY-SA 4.0
2024-08-13T10:18:41.767Z
What do you mean by "how is witness usually modeled in an NL Turing machine"? An NL Turing machine has no witnesses; it is just a nondeterministic Turing machine (with a read-only input tape and logarithmic-size work tapes). This, as you note, is equivalent to a deterministic logspace machine equipped with a read-once polynomial-size witness tape.
Emil Jeřábek
CC BY-SA 4.0
2024-08-13T10:20:01.167Z
With an unrestricted polynomial-size witness tape, you get NP (easy exercise).
Emil Jeřábek
CC BY-SA 4.0
2024-08-13T19:55:12.133Z
@EmilJeřábek yeah I get it now, I have heard something similar about how a Logspace TM with unlimited access to polysize witness is a lot stronger than NL. Thanks for confirming!
kingoyster
<cc.complexity-theory><reference-request><logspace>
Witness for NL Computation
kingoyster
# Witness for NL Computation

(Asked by: username_0 on 2024-08-13)

For any NP language, we usually describe the language as having a polynomial time TM M such that for yes instance x you can find a witness such that M(x, w) accepts and for no instance M will not accept x no matter what the witness is.

I know that nondeterminism refers to transition in a state machine, so technically the witness w is read once only (you shouldn’t be allowed to rewind) but in the case of NP we can bypass this restriction by recording w locally and rewind all we want.

However, for NL it seems like you can’t do shouldn’t be allowed to rewind back to earlier parts of witness w as you can’t simulate the rewinding due to space constraints.

My question is, how is witness w usually modeled in an NL Turing Machine and how would the language be different if we are allowed to rewind witness in such TM?

**Tags:** cc.complexity-theory, reference-request, logspace
> **Comments:**
> **username_1**: What do you mean by "how is witness usually modeled in an NL Turing machine"? An NL Turing machine has no witnesses; it is just a nondeterministic Turing machine (with a read-only input tape and logarithmic-size work tapes). This, as you note, is equivalent to a deterministic logspace machine equipped with a read-once polynomial-size witness tape.  
> **username_1**: With an unrestricted polynomial-size witness tape, you get NP (easy exercise).  
> **username_0**: @EmilJeřábek yeah I get it now, I have heard something similar about how a Logspace TM with unlimited access to polysize witness is a lot stronger than NL. Thanks for confirming!  

---

## 0 answers

