yea, but
regular TM has no witness tape that it has to check. i just found an exercise (slightly) dealing with this question, it may make things clearer: Let us define the class NL* to be the class of all languages L for which there is a TM with the following criteria: Input tape: Read only, move in both directions Witness tape: Read only, Move in both directions Work tape: Read-Write, Move in both directions. The machine itself is deterministic (the guesses are value of the wirness tape). The soace complexity is the size of the work tape, and is bounded by O(lgn). We say the machine accepts an input x if and only if there exist a setting for the witness tape, with which the machine returns TRUE (a) prove that NP c NL* (b) conclude that if P != NP then NL != NL* solution: given a formula θ and a witness γ, we check that γ encodes a valid truth assignment for θ and that each clause of θ us satisfied by γ. we only need logarithmic space for indices, and obviously θ e 3SAT iff we accept θ,γ. -- what i dont understand is, how did the fact that we can move in both directions in the witness tape helped us verify the encoding? because without this property this is normal NL, which according to (b) is most likely != NL. still, to my intuition it looks like you can do it with one direction Witness tape: we only require that there will be some witness tape that "fits", so we can require that the encoding in the witness tape will be sorted in the same way that the literlas are sorted inside θ and then just go over it and check that this assignment does satisfy each caluse. mm this obviously doesnt work when θ has more then 1 occurence per literal.. this may be the problem...
