<p>According to <a href="https://cstheory.stackexchange.com/questions/93/what-are-the-best-current-lower-bounds-on-3sat">"What are the best current lower bounds on 3SAT?"</a>, Ryan Williams has an answer that states that the (time * space) requirements for 3-SAT must meet or exceed $n^{2 \cos(\pi/7) - o(1)}$ infinitely often.  See</p>

<pre><code> Ryan R. Williams
 Better Time-Space Lower Bounds for SAT and Related Problems
 20th IEEE Conference on Computational Complexity, pages 40-49
 2005
</code></pre>

<p>...or his link <a href="http://www.cs.cmu.edu/~ryanw/automated-lbs.pdf" rel="nofollow noreferrer">here</a>.</p>

<p>If we consider Atkin and Bernstein's sieve:</p>

<pre><code> A.O.L Atkin and D.J. Bernstein
 Prime sieves using binary quadratic forms
 Mathematics of Computation, Volume 73, Number 246, pages 1023-1030
 December 19, 2003
</code></pre>

<p>...It requires $O(\frac{n}{\log \log n})$ additions and $n^{1/2 + O(1)}$ space.  So does this sieve alone meet the time/space requirements for 3-SAT?  Or are the results inconclusive for the sieve?</p>

CC BY-SA 3.0
2014-03-15T00:16:45.390Z
I must be missing something: what does a prime sieve have to do with 3SAT ?
Suresh Venkat
CC BY-SA 3.0
2014-03-15T01:04:33.970Z
@SureshVenkat:  I'm working with a residue number system in a 3-SAT algorithm.  I was just wondering if the sieve itself would meet the lower bound requirements.  I now know that the algorithm itself far exceeds the requirements.  I can withdraw the question, if this now seems inappropriate.
Matt Groff
<sat><lower-bounds>
Does this meet the space requirements for the lower 3-SAT bounds?
Matt Groff
# Does this meet the space requirements for the lower 3-SAT bounds?

(Asked by: username_0 on 2014-03-14)

According to "What are the best current lower bounds on 3SAT?", Ryan Williams has an answer that states that the (time * space) requirements for 3-SAT must meet or exceed $n^{2 \cos(\pi/7) - o(1)}$ infinitely often.  See
 Ryan R. Williams
 Better Time-Space Lower Bounds for SAT and Related Problems
 20th IEEE Conference on Computational Complexity, pages 40-49
 2005

...or his link here.
If we consider Atkin and Bernstein's sieve:
 A.O.L Atkin and D.J. Bernstein
 Prime sieves using binary quadratic forms
 Mathematics of Computation, Volume 73, Number 246, pages 1023-1030
 December 19, 2003

...It requires $O(\frac{n}{\log \log n})$ additions and $n^{1/2 + O(1)}$ space.  So does this sieve alone meet the time/space requirements for 3-SAT?  Or are the results inconclusive for the sieve?

**Tags:** sat, lower-bounds
> **Comments:**
> **username_1**: I must be missing something: what does a prime sieve have to do with 3SAT ?  
> **username_0**: @SureshVenkat:  I'm working with a residue number system in a 3-SAT algorithm.  I was just wondering if the sieve itself would meet the lower bound requirements.  I now know that the algorithm itself far exceeds the requirements.  I can withdraw the question, if this now seems inappropriate.  

---

## 0 answers

