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

Promise-Ball-k-SATInput:Objective: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:

Related