1
$\begingroup$

We are given a Boolean formula $F$ in conjunctive normal form with $n$ variables and $m$ clauses and we would like to know if there exists at least one assignment to the $n$ variables that makes $F$ evaluate to True. As we all know this is the famous NP-Complete SAT problem. I would like to know the consequences of being able to solve this problem in time ${\bf O}$($m$). Would this contradict the Phase transition phenomenon that has been shown to exists for the SAT problem? Thank You

PS:If you do not allow repetition of variables in a clause nor repetition of clauses in a formula then you can have up to 3$^{n}$-1 unique clauses.

$\endgroup$
  • 6
    $\begingroup$ This is a polynomial-time algorithm, and would imply that P = NP. $\endgroup$ – George Feb 28 '13 at 15:33
  • 1
    $\begingroup$ @George number of clauses $m$ could be exponential in terms of number of variables $n$. $\endgroup$ – user13970 Feb 28 '13 at 15:42
  • 9
    $\begingroup$ @user13970: No. The input length means the total length of the input. This notion does not change from problem to problem, so there is nothing special "when we talk about the input length of SAT". $\endgroup$ – Huck Bennett Feb 28 '13 at 17:34
  • 2
    $\begingroup$ In computational complexity the focus is usually on worst-case analysis. This means that of interest are sparse instances of SAT (where $m = O(n^k)$ for some constant $k$), precisely because in the general case SAT instances can have $m = \Omega(2^n)$. Such dense instances are not that interesting from a computational complexity point of view, since (as you state) they can be solved in linear time. $\endgroup$ – András Salamon Feb 28 '13 at 17:57
  • 6
    $\begingroup$ @user13970: A 3SAT instance cannot have more than $8 n^3$ different clauses (assuming all clauses have exactly three literals; more generally it will be $O(n^3)$). $\endgroup$ – sdcvvc Feb 28 '13 at 18:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy