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$ Jun 22, 2018 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, 2018 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, 2018 at 21:39
  • $\begingroup$ @usul n is the length of boolean formula(sat) and not the length of input bits. $\endgroup$ Jun 25, 2018 at 10:47
  • $\begingroup$ @EmilJeřábek I think you can copy your comment to this question's answer. thank you again. $\endgroup$ Jun 25, 2018 at 10:49

1 Answer 1


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 and acknowledge you have read our privacy policy.

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