1
$\begingroup$

Consider the following naïve argument that any algorithm solving SAT must take $\Omega(2^n)$ time in the worst-case scenario.

Let $f(x_1,x_2,\dots,x_n)$ be a Boolean function in conjunctive normal form (CNF). The problem SAT is to determine whether there exists a $(x_1,x_2,\dots,x_n) \in \{0,1\}^n$ such that $f(x_1,x_2,\dots,x_n)=1$. Nothing is known a priori about the function $f$, so in general, in order to determine this information, it is necessary to plug in each $(x_1,x_2,\dots,x_n) \in \{0,1\}^n$ into $f(x_1,x_2,\dots,x_n)$ to test whether $f(x_1,x_2,\dots,x_n)=1$, until one is found to satisfy $f$ or all are found not to satisfy $f$. There are $2^n$ possible $(x_1,x_2,\dots,x_n) \in \{0,1\}^n$ to plug into $f(x_1,x_2,\dots,x_n)$ to test. Therefore, any algorithm solving SAT must take $\Omega(2^n)$ time in the worst-case scenario. So $P \neq NP$. QED

What exactly is wrong with this argument? More importantly, are there any known counterexamples (algorithms that take $o(2^n)$ in the worst case scenario for SAT)?

Caveat: Note that there are known counterexamples if one restricts $f$ to being in 3CNF, but this is only because 3CNF has a special structure that plain CNF does not have. Plain CNF has no special structure at all, since any Boolean function can be placed in CNF.

$\endgroup$
  • 4
    $\begingroup$ "it is necessary to plug in each..." -- proof needed. $\endgroup$ – Raphael Jan 4 '18 at 18:03
  • $\begingroup$ And yes, there are plenty of non-trivial algorithms for NP-complete problems, some even with sub-exponential running-times. (And using the poly-time reduction, each of them can be used to solve SAT in similar time.) $\endgroup$ – Raphael Jan 4 '18 at 18:04
  • 1
    $\begingroup$ More generally, you can look at the literature for exact (exponential-time) algorithms. You will see that there are many difficult problems for which it is possible to do better than brute-force search, like you are suggesting for SAT. $\endgroup$ – Juho Jan 4 '18 at 18:18
  • 2
    $\begingroup$ @CraigFeinstein For SAT in particular you could look at the strong exponential-time hypothesis (SETH). $\endgroup$ – Juho Jan 4 '18 at 18:40
  • 1
    $\begingroup$ FWIW, my earlier comment is wrong as far as this question is concerned. Since reductions can blow up instance sizes polynomially, a subexponential algorithm for one NP-complete problem does not automatically yield one for another. $\endgroup$ – Raphael Jan 4 '18 at 23:02
11
$\begingroup$

The error in your argument is the claim

Nothing is known a priori about the function $f$, (...) so it is necessary to plug in all $2^n$ values.

, which is simply false. I will demonstrate why it isn't necessary to plug in all possible values and sketch how to arrive at an $O^*((2^k-1)^{n/k})$ time algorithm, where $k$ is the number of clauses. $O^*$ 'hides' poly-logarithmic factors, so for fixed $k$, this would be an $o(2^n)$ algorithm.

A key idea is this: If we wish to satisfy some clause of $m$ literals $l_1 \vee l_2 \vee \dots\vee l_m$ by assigning truth-values, then there are $2^m-1$ ways to do this, as exactly one of the assignments does not satisfy the formula. This means we in fact do not have to test every assignment (for this clause).

Not doing a single test seems like a trivial improvement. However, by recursively applying the procedure to only check at most $2^k-1$ assignments, we get a running time $T(n)$ for which we have $T(n)= (2^{m_i}-1)\cdot T(n-m_i) + O^*(n)$, where $m_i$ is the number of elements of the $i$-th clause. So, $T(n) = (\Pi_{i=1}^l (2^{m_i}-1))T(0)+l\cdot O^*(n)$, where $l$ is the number of clauses. This gives the result $T(n)=O^*((2^k-1)^{n/k})$.

Of course, our improvement still yields a rather unpractical algorithm, but there are other tricks you can apply. To learn more, these slides by William Gasarch are a good read. (The title states 3-SAT, but most methods can be generalised to $k$-SAT)

$\endgroup$
  • $\begingroup$ I wouldn't call an exponential speedup "minimal". O.o $\endgroup$ – Raphael Jan 4 '18 at 19:25
  • $\begingroup$ @Raphael Well, my main point is that the improved algorithm is still rather unpractical. But perhaps I should phrase that differently. $\endgroup$ – Discrete lizard Jan 4 '18 at 19:33
  • $\begingroup$ Ah, never mind. I read that wrong. It's only the $-1$ that's the speedup, not the $\_^{1/k}$. Indeed, not a lot. $\endgroup$ – Raphael Jan 4 '18 at 19:38
  • $\begingroup$ I wouldn't call it an exponential speedup; it only works when k is fixed. But my naive argument is for general $f$. However, it is a good answer, as it sheds light upon things. $\endgroup$ – Craig Feinstein Jan 4 '18 at 19:39
  • $\begingroup$ It's an exponential speedup that vanishes as $k$ tends to infinity. By the strong exponential time hypothesis, any speedup for some $k$ wrt. to $O(2^n)$ vanishes as $k$ tends to infinity. So the full extent of your question is in fact a (hard) open problem. $\endgroup$ – Discrete lizard Jan 4 '18 at 19:59
8
$\begingroup$

The answer is simple, many times the naive impression is wrong, and one can find a more clever method to solve the problem.

This actually happens a lot in computer science. Clearly one cannot share secrets with an unfamiliar party in a public channel, however public key cryptography was developed. Obviously one cannot prove a theorem without revealing the ideas of the proof, well, zero knowledge proofs exist. Obviously in order to reduce the error of a randomized algorithm which uses $n$ coins from $p$ to $p^k$ one needs $nk$ coins, again, using a more sophisticated approach one can do better.

Even for general SAT there is no need to go over every assignment. If some partial assignment $g: S\rightarrow\{0,1\}$, where $S\subseteq\{x_1,...,x_n\}$ is some subset of variables, does not satisfy some clause, then you can tell immediately that every extension of $g$ will not satisfy the given CNF. Note that an $O\left(2^{(1-\epsilon)n}\right)$ algorithm would contradict the strong exponential time hypothesis, so you will not find such an algorithm in the current literature.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.