patternMinor
Is SAT is in NL?( under certain conditions)
Viewed 0 times
satundercertainconditions
Problem
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?
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?
Solution
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.
Context
StackExchange Computer Science Q#18061, answer score: 4
Revisions (0)
No revisions yet.