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

...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?

  • 3
    $\begingroup$ I must be missing something: what does a prime sieve have to do with 3SAT ? $\endgroup$ – Suresh Venkat Mar 15 '14 at 0:16
  • $\begingroup$ @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. $\endgroup$ – Matt Groff Mar 15 '14 at 1:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.