# What is best known space requrement for solving SATISFIABILITY problem in exp time

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.

• If it were solvable in space $o(n)$, itwould be solvable in time $2^{o(n)}$, contradicting the exponential-time hypothesis. – Emil Jeřábek Jun 22 '18 at 13:35
• 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. – Yonatan N Jun 22 '18 at 19:05
• @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. – usul Jun 24 '18 at 21:39
• @usul n is the length of boolean formula(sat) and not the length of input bits. – Mohsen Ghorbani Jun 25 '18 at 10:47
• @EmilJeřábek I think you can copy your comment to this question's answer. thank you again. – Mohsen Ghorbani Jun 25 '18 at 10:49