0
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • 3
    $\begingroup$ I must be missing something: what does a prime sieve have to do with 3SAT ? $\endgroup$
    – Suresh Venkat
    Mar 15, 2014 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, 2014 at 1:04

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.