Naive argument that P ≠ NP

Question

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.

Answer 1

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)

Answer 2

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.