This preprint was accepted June 28, 2002
Contact:
E. Hirsch and A. Kulikov
ABSTRACT:
The exact 3-satisfiability problem (X3SAT) is: given a Boolean formula in 3-CNF, find a truth assignment, such that
exactly one literal in each clause is set to true. It is well-known that X$3$SAT is NP-complete. In this paper, we present an exact algorithm solving X3SAT in time $O(2^{n/6.15})$, where $n$ is the number of variables.
This bound improves the previously known bound $O(2^{n/5.35})$ of \cite{PRS02}
(where also the bound $O(2^{n/6})$ was announced).
[Full text:
(.ps.gz)]