Lesson 4

Let's now show how to use local search to get stronger bounds!

Theorem. Let \(F\) be a 3-CNF formula on \(n\) variables, and \(\alpha \in \{0,1\}^{n}\) an assignment to the variables. Checking for a satisfying assignment for \(F\) in the ball \[\operatorname{Ball}(\alpha, r)=\{u \in \{0,1\}^{n} \colon \operatorname{dist}(\alpha, u) \le r\}\] can be done in time \(O^{*}(3^{r})\).

Proof. Suppose right away that there exists a satisfying assignment \(\beta \in \{0,1\}^{n}\) in the ball: if not, we will still spend \(O^{*}(3^{r})\) and return nothing. At each moment we will be at some assignment \(\gamma \in \{0,1\}^{n}\), initially \(\gamma=\alpha\). If \(\gamma\) satisfies the formula, we stop with a shout of “hooray!”. Otherwise, take a clause \(C\) violated by \(\gamma\), and assume it depends on variables \(x_{i}, x_{j}, x_{k}\). A simple but important observation: \(\beta\) assigns at least one of these variables to the opposite of \(\gamma\) (otherwise \(\beta\) would also violate this clause!). So we do the following: make recursive calls for the three assignments obtained from \(\gamma\) by flipping \(x_{i}\), \(x_{j}\), and \(x_{k}\). In one of these branches we move closer to \(\beta\). We don’t know, of course, which one, but that’s okay. Building such a tree of depth \(r\), we are guaranteed to find \(\beta\) and spend at most \(O^{*}(3^{r})\) time.◼

Theorem. The 3-satisfiability problem can be solved in time \(O^{*}(1{,}74^{n})\) by a deterministic algorithm and in time \(O^{*}(1{,}5^{n})\) by a probabilistic algorithm.

Proof. The whole space can be covered by two balls of radius \(\frac{n}{2}\), so it suffices to check the balls \(\operatorname{Ball}(0^{n}, n/2)\) and \(\operatorname{Ball}(1^{n}, n/2)\). The running time will then be \(O^{*}(3^{n/2})=O^{*}(1{,}73\dotsc^{n})\).

Balls of radius \(\frac{n}{4}\) would already require exponentially many, and it’s not clear how to cover everything with fewer such balls. So we use a standard trick: choose the ball’s center randomly and search in it. The success probability in one step equals \(p=\frac{\operatorname{Vol}(n/4)}{2^n}\). Hence, after \(\frac{1}{p}\) repetitions the success probability becomes constant. The running time is \[O^{*}\left(3^{\frac{n4}}\cdot \frac{2^n}{\operatorname{Vol}(n/4)}\right)= O^{*}\left(2^{\frac{n\log 3}{4}}\cdot 2^{n-n(\frac{1}{4}\cdot \log 4 + \frac{34}{\cdot} \log \frac{4}{3})}\right)= O^{*}\left(\left(\frac{3}{2}\right)^{n}\right) \ .\]◼