2
$\begingroup$

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.

Improve this question
$\endgroup$
13
  • 3
    $\begingroup$ Your question is equivalent to the question "P=NP?". $\endgroup$
    – Kevin H. Lin
    Commented Jun 10, 2010 at 6:39
  • 4
    $\begingroup$ There isn't a gray area. It's not that SAT is not in P and is not outside P either, as you say. Either it is in, or it's not. $n^{g(n)}$ is the latter, and only the latter. $\endgroup$
    – Dror Speiser
    Commented Jun 10, 2010 at 7:25
  • 7
    $\begingroup$ It sounds like the question you mean to ask is for which k one can unconditionally prove that SAT is not solvable in time n^k. This question might be sensitive to your model of computation; I'm sure there are experts here who can comment on that. $\endgroup$
    – David E Speyer
    Commented Jun 10, 2010 at 7:29
  • 3
    $\begingroup$ @Wang Zirui: The phrase "the standard model, i.e. Turing machine" is misleading in this context. There are many different Turing machine models, depending on whether one allows for multiple tapes, multiple read/write heads, etc., along with other types of models such as register machines. See the wikipedia page <a href="en.wikipedia.org/wiki/… machine equivalents</a> for examples. Each can simulate the others in polynomial time, so the class P is well-defined and independent of the chosen model, but "computable in TIME(n^k)" depends on the model. $\endgroup$
    – Noah Stein
    Commented Jun 10, 2010 at 12:55
  • 1
    $\begingroup$ I would strongly encourage someone who understands this better than me to rewrite the question so that it makes clear that it's asking the negative of the question it actually asks, that clarifies the models issue, and removes the errors. I tried to do so myself but concluded that I don't understand the issues well enough to do so confidently. $\endgroup$
    – Noah Snyder
    Commented Jun 10, 2010 at 14:06

3 Answers 3

Reset to default
7
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Do you mean Wolfgang J. Paul's A 2.5n-lower bound on the combinational complexity of Boolean functions? Also please read Corollary 6 on page 10 in Ben-David and Halevi's paper; it doesn't have the quantifications you mentioned, and it's a theorem. $\endgroup$
    – Zirui Wang
    Commented Jun 10, 2010 at 14:28
  • $\begingroup$ Corollary 6 also has the "any method known today" clause, which is the most important caveat. As for the best lower bound, it depends on the model -- boolean circuits, one tape TMs, two tape TMs, etc. See the question I linked to for some very good answers by people who understand this area much better than I do. $\endgroup$
    – Rune
    Commented Jun 11, 2010 at 2:22
  • $\begingroup$ No, I'm not talking about lower bounds. Yes, a high lower bound implies that the problem can't be solved in any time less. But a lower bound is overkill because it's possible that the lower bound is low and yet the problem can't be solved in time higher than the lower bound. For example, the best lower bound for SAT could be linear. But it's still possible to prove that no quadratic SAT solver exists. $\endgroup$
    – Zirui Wang
    Commented Jun 11, 2010 at 8:18
  • $\begingroup$ But I found the answer to my question in Cook's article: claymath.org/millennium/P_vs_NP/pvsnp.pdf He says "It is consistent with present knowledge that not only could Satisfiability have a polynomial-time algorithm, it could have a linear time algorithm on a multitape Turing machine." Note that multitape Turing machine is the standard model. $\endgroup$
    – Zirui Wang
    Commented Jun 11, 2010 at 8:20
3
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Thanks, but what I want is a negative answer, i.e. SAT can't be solved in, for example, linear time. If it can, great--P = NP. But if you can prove that linear time is not sufficient to solve SAT--although this does not mean P $\ne$ NP--I think it's a GREAT result still. $\endgroup$
    – Zirui Wang
    Commented Jun 10, 2010 at 13:08
2
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I discussed "the impossibility of an improved SAT algorithm" (sort of) under the assumption that P = NP is independent of ZFC in this question: mathoverflow.net/questions/27959 $\endgroup$
    – Zirui Wang
    Commented Jun 12, 2010 at 18:54
  • $\begingroup$ @Suresh: But thanks for the reference! It's certainly an interesting paper that has widened my thought. $\endgroup$
    – Zirui Wang
    Commented Jun 16, 2010 at 9:25

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .