I searched a lot for finding best space requirement algorithm for SATISFIABILITY problem but I didn't find any thing better than brute force that is in DSPACE(n). is there exists better bound? and what is best known bound.

  • 12
    $\begingroup$ If it were solvable in space $o(n)$, itwould be solvable in time $2^{o(n)}$, contradicting the exponential-time hypothesis. $\endgroup$ – Emil Jeřábek Jun 22 '18 at 13:35
  • 5
    $\begingroup$ From the opposite direction, any $\omega(\log n)$ lower bound would imply $\bf{L} \neq \bf{NP}$, which is itself an open problem. A $\log n$ lower bound is trivial. $\endgroup$ – Yonatan N Jun 22 '18 at 19:05
  • $\begingroup$ @MohsenGhorbani,, when you write $n$, do you mean the number of variables or the number of bits of the input? There is perhaps a small difference here. $\endgroup$ – usul Jun 24 '18 at 21:39
  • $\begingroup$ @usul n is the length of boolean formula(sat) and not the length of input bits. $\endgroup$ – Mohsen Ghorbani Jun 25 '18 at 10:47
  • $\begingroup$ @EmilJeřábek I think you can copy your comment to this question's answer. thank you again. $\endgroup$ – Mohsen Ghorbani Jun 25 '18 at 10:49

If I understand your question correctly, as far as I understand this is computational-model dependent. An excellent lecture on the subject by Prof. Ryan O'Donnell can be found here: https://www.youtube.com/watch?v=_nCBH_lVjGU


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.