28 August 2010

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

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

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

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.


Leave a Comment »

No comments yet.

RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Create a free website or blog at

%d bloggers like this: