Can SAT be solved in time n^k, for a specific k? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-20T07:01:38Z http://mathoverflow.net/feeds/question/27651 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/27651/can-sat-be-solved-in-time-nk-for-a-specific-k Can SAT be solved in time n^k, for a specific k? Zirui Wang 2010-06-10T06:26:53Z 2010-06-12T05:55:25Z <p>The P vs NP problem is open. How about the following questions--Can SAT be done in \$n^k\$ time for some specific \$k\$?</p> <p>Why do I ask these questions? Ben-David and Halevi's paper <a href="http://www.cs.technion.ac.il/~shai/ph.ps.gz" rel="nofollow">On the independence of P versus NP</a> proves that if P = NP is independent of PA, then SAT can be solved in \$n^{g(n)}\$ time, where \$g\$ is a very slow, almost constant function. This means that if we can neither prove nor disprove SAT is in P, then SAT lies on the boundary of P. It's not in P and it's not outside P either. So there's a gray area near the boundary of P. Because of this possibility, I think the P vs NP problem is not a good formulation. I therefore propose to ask more precise questions like whether SAT can be solved in linear/quadratic/cubic/etc time.</p> http://mathoverflow.net/questions/27651/can-sat-be-solved-in-time-nk-for-a-specific-k/27678#27678 Answer by Christoph-Simon Senjak for Can SAT be solved in time n^k, for a specific k? Christoph-Simon Senjak 2010-06-10T10:52:35Z 2010-06-10T10:52:35Z <p>As far as I know SAT is NP-Complete. Therefore, if there was such a \$k\$ as you said, then SAT would be in \$P\$, because, you know, \$n^k\$ is a polynomial. Thus, finding such a \$k\$ would prove \$P=NP\$.</p> http://mathoverflow.net/questions/27651/can-sat-be-solved-in-time-nk-for-a-specific-k/27690#27690 Answer by Rune for Can SAT be solved in time n^k, for a specific k? Rune 2010-06-10T13:21:23Z 2010-06-10T13:21:23Z <p>It seems you are looking for lower bounds on SAT, not upper bounds. In that case, see <a href="http://mathoverflow.net/questions/4953/super-linear-time-complexity-lower-bounds-for-any-natural-problem-in-np" rel="nofollow">this question</a> I asked here a while ago. In short, the best lower bounds we have for SAT are linear, so can't even say that SAT cannot be solved in O(n) time.</p> <p>Secondly I would just like to point out that Ben-David and Halevi's paper does not claim what you wrote. It says that if P vs NP is proved to be independent of PA (or ZFC) <strong>using currently known techniques</strong> then NP is contained in DTIME(\$n^{g(n)}\$) for infinitely many inputs, where g(n) is an extremely slow growing function. Note the "infinitely many inputs" part, and most importantly, the "using currently known techniques" part.</p> http://mathoverflow.net/questions/27651/can-sat-be-solved-in-time-nk-for-a-specific-k/27906#27906 Answer by Suresh Venkat for Can SAT be solved in time n^k, for a specific k? Suresh Venkat 2010-06-12T05:55:25Z 2010-06-12T05:55:25Z <p>You might find <a href="http://www.cs.cmu.edu/~ryanw/cnf-sat-feasible.pdf" rel="nofollow">this paper</a> by Patrascu and Williams interesting. It surveys the state of the art for SAT, as well as discussing implications for improved bounds. </p>