<p>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: <a href="https://www.youtube.com/watch?v=_nCBH_lVjGU" rel="nofollow noreferrer">https://www.youtube.com/watch?v=_nCBH_lVjGU</a></p>

CC BY-SA 4.0
2018-07-05T17:03:49.283Z
2018-07-05T17:03:49.283Z
Avi Tal
<p>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.</p>

CC BY-SA 4.0
2018-06-22T13:35:53.853Z
If it were solvable in space $o(n)$, itwould be solvable in time $2^{o(n)}$, contradicting the exponential-time hypothesis.
Emil Jeřábek
CC BY-SA 4.0
2018-06-22T19:05:47.687Z
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
CC BY-SA 4.0
2018-06-24T21:39:19.617Z
@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
CC BY-SA 4.0
2018-06-25T10:47:01.053Z
@usul n is the length of boolean formula(sat) and not the length of input bits.
Mohsen Ghorbani
CC BY-SA 4.0
2018-06-25T10:49:26.323Z
@EmilJeřábek I think you can copy your comment to this question's answer. thank you again.
Mohsen Ghorbani
CC BY-SA 4.0
2018-06-25T14:02:52.457Z
I have voted to close, as this is not a research-level question. It would not be appropriate for me to post an answer at the same time. I will be happy to answer it if you take the question to https://cs.stackexchange.com .
Emil Jeřábek
<cc.complexity-theory><sat><space-complexity>
What is best known space requrement for solving SATISFIABILITY problem in exp time
Mohsen Ghorbani
# What is best known space requrement for solving SATISFIABILITY problem in exp time

(Asked by: username_0 on 2018-06-22)

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.

**Tags:** cc.complexity-theory, sat, space-complexity

> **Comments:**
> **username_1**: If it were solvable in space $o(n)$, itwould be solvable in time $2^{o(n)}$, contradicting the exponential-time hypothesis.  
> **username_2**: 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.  
> **username_3**: @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.  
> **username_0**: @username_3 n is the length of boolean formula(sat) and not the length of input bits.  
> **username_0**: @EmilJeřábek I think you can copy your comment to this question's answer. thank you again.  
> **username_1**: I have voted to close, as this is not a research-level question. It would not be appropriate for me to post an answer at the same time. I will be happy to answer it if you take the question to https://cs.stackexchange.com .  

---

## 1 answers

### Answer by username_4 on 2018-07-05. Score: 3 | Accepted answer

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>


---

