###
Steklov Institute of Mathematics at St.Petersburg

#
PREPRINT 13/2002

Edward A. HIRSCH and Alexander S. KULIKOV
##
A $2^{n/6.15}$-TIME ALGORITHM FOR X3SAT

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)]

Back to all preprints

Back to the Steklov
Institute of Mathematics at St.Petersburg