The paper notably rephrases Schöning’s search problem as
Promise-Ball-k-SAT
Input:
-CNF formula with variables, an assignment , a natural number , and a promise that there is a satisfying assignment within Hamming distance of .
Objective:
find a satisfying assignment for F.
Note that the satisfying assignment does not have to be in the -ball centered at .
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 and arity in time . In contrast, a straightforward brute-force approach takes time.
deterministic 3SAT in O*(1.334^n) time
Tags: papers
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,
for any 
. For 
, this is 
.
The paper notably rephrases Schöning’s search problem as
Note that the satisfying assignment does not have to be in the
-ball centered at 
.
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
and arity 
in time 
. In contrast, a straightforward brute-force approach takes 
time.
Like this: