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.

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top