2
$\begingroup$

Consider a certicate for 3SAT that lists an assignment for each occurrence of a variable in the order of appearence,e.g. 100000 for ($x\bigvee$$y\bigvee$z)$\bigwedge$($\neg(w)$$\bigvee$$y\bigvee$z). This certicate is of polynomial length and can be read once to check the satisability of the given formula. Does this prove that SAT is in NL?

$\endgroup$
2
  • 2
    $\begingroup$ If SAT in in NL. Then P=NP as NL is in P. So this is not possible. Is the definition of NL used here correct? Do you need to make sure that the certificate does not assign 0 and 1 to the same variable in different clauses? $\endgroup$ – e_noether Nov 16 '13 at 3:17
  • $\begingroup$ Read carefully above Question Under Certain Conditions !! $\endgroup$ – Harshil Sep 26 '14 at 14:04
2
$\begingroup$

The certificate could have linear size, and you need to remember it for the entire verification process. That is, you need to store in on the work tape and reference it as you read the clauses. You can't guess a satisfying assignment for each clause separately - under this model, every 3CNF is satisfiable. The oracle tape is consumed by each read - you can't go back and reread a previous symbol, which might be what's confusing you.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.