Certificate Definition of NL

Question

As per the Sanjeev Arora book, for a certificate based definition of $NL$, the machine is allowed a "read-once" certificate tape to store the certificate along with $O(log n)$ read/write work tape for a deterministic verifier machine.

My doubt is that for a $3-SAT$ problem, if instead of storing an assignment to the $n$ variables, I store the $3k$ assignments to the $3k$ literals in a $k$ clause 3-SAT formula in the certificate tape. This way I don't have to re-read a previous symbol and I can go from left to right in the certificate tape at each step of the machine.

And in work tape I can calculate OR of 3 literals. If it is $0$, then I reject, if it is $1$, I erase the contents of the work tape and store the values of 3 literals of the next clause, and repeat. If all clauses were satisfying, I accept.

The certificate is also polynomial in the length of input. Kindly point out the flaw in this argument, otherwise $3-SAT$ would $\in NL$, which is not believed to be true.

Answer 1

The problem is that you won't be able to verify if the certificate is legitimate as you are making certificate with assignment of variables clause by clause. To check it is legitimate you would have to traverse back on certificate tape which you won't be able to. For example let $\phi = \{ (x_1 \vee x_2 \vee x_3) \wedge (\overline{x_1} \vee x_4 \vee x_5) $. And say your certificate is {(True,False,False),(True,False,False)}. In this case you would declare that assignment makes $\phi$ True but that's not the case as $x_1$ and $\overline{x_1}$ can't both be True and to check all assignments are valid you will have to traverse back and forth on certificate tape which you can't do. Thus your approach is not correct.