Can SAT be solved in time n^k, for a specific k? - MathOverflow

Can SAT be solved in time n^k, for a specific k?

2010-06-10T06:26:53Z

The P vs NP problem is open. How about the following questions--Can SAT be done in $n^k$ time for some specific $k$?

Why do I ask these questions? Ben-David and Halevi's paper On the independence of P versus NP 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.

Answer by Christoph-Simon Senjak for Can SAT be solved in time n^k, for a specific k?

2010-06-10T10:52:35Z

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

Answer by Rune for Can SAT be solved in time n^k, for a specific k?

2010-06-10T13:21:23Z

It seems you are looking for lower bounds on SAT, not upper bounds. In that case, see this question 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.

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) using currently known techniques 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.

Answer by Suresh Venkat for Can SAT be solved in time n^k, for a specific k?

2010-06-12T05:55:25Z

You might find this paper by Patrascu and Williams interesting. It surveys the state of the art for SAT, as well as discussing implications for improved bounds.