# Constraints

## 28 August 2010

### deterministic 3SAT in O*(1.334^n) time

Filed under: Commentary — András Salamon @ 0:31
Tags:

Robin Moser and Dominik Scheder have put an end to the stream of slight improvements in derandomizing Schöning’s randomized k-SAT algorithm from 1999.

In A Full Derandomization of Schöning’s k-SAT Algorithm, Moser and Scheder show how to achieve worst-case runtime as close as desired to the runtime of the randomized algorithm, ${O^{*}((2\frac{k-1}{k}+\epsilon)^n)}$ for any ${\epsilon > 0}$. For ${k = 3}$, this is ${O^{*}((1.334+\epsilon)^n)}$.

The paper notably rephrases Schöning’s search problem as

 Promise-Ball-k-SAT Input: ${k}$-CNF formula ${F}$ with ${n}$ variables, an assignment ${x}$, a natural number ${r}$, and a promise that there is a satisfying assignment within Hamming distance ${r}$ of ${x}$. Objective: find a satisfying assignment for F.

Note that the satisfying assignment does not have to be in the ${r}$-ball centered at ${x}$.

Instead of using a Boolean covering code (with a domain of two values) as is done by Dantsin et al., Moser and Scheder use a covering code with a domain containing more values. Larger domains allow a closer approximation to the runtime bound.

A neat application (Corollary 13) is that it is possible to solve the constraint satisfaction problem with domain size ${d}$ and arity ${k}$ in time ${O^{*}((d\frac{k-1}{k} + \epsilon)^n)}$. In contrast, a straightforward brute-force approach takes ${O^{*}(d^n)}$ time.