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.
$\begingroup$
$\endgroup$
6
asked Jun 22, 2018 at 12:39
-
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řábekCommented 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 NCommented 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$– usulCommented Jun 24, 2018 at 21:39
-
$\begingroup$ @usul n is the length of boolean formula(sat) and not the length of input bits. $\endgroup$– Mohsen GhorbaniCommented 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$– Mohsen GhorbaniCommented Jun 25, 2018 at 10:49
|
Show 1 more comment
1 Answer
$\begingroup$
$\endgroup$
0
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
