How to prove that SAT is in L if and only if NP=L? I know that reducing SAT in cook-levin theorem is computable in deterministic linear space . How to do it in log space? Any reference will also help.

  • $\begingroup$ Schaefer in his paper THE COMPLEXITY OF SATISFIABILITY PROBLEMS stated (unfortunately without a proof), that every NP problem is log-space reducible to 3-SAT. If it's true then if SAT is in L then every NP problem is in L, so it may be good idea to find a proof of that. $\endgroup$ – Szymon Stankiewicz Oct 27 '17 at 8:59
  • $\begingroup$ The usual proof of the Cook–Levin theorem can be implemented in logspace. You don't have to do anything special. $\endgroup$ – Yuval Filmus Oct 27 '17 at 9:25

Your Answer

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

Browse other questions tagged or ask your own question.