0

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?

Community
  • 1
Matt Groff
  • 2,100
  • 13
  • 19
  • 3
    I must be missing something: what does a prime sieve have to do with 3SAT ? – Suresh Venkat Mar 15 '14 at 00:16
  • @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 Mar 15 '14 at 01:04

0 Answers0