Geodesic
An upper bound $O(2^{0.16254n})$ for Exact 3-Satisfiability: a simpler proof
Zapiski Nauchnykh Seminarov POMI, Computational complexity theory. Part VII, Tome 293 (2002), pp. 118-128

Voir la notice de l'article provenant de la source Math-Net.Ru

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 X3SAT is NP-complete. In this paper, we present an exact algorithm solving X3SAT in time $O(2^{0.162536n})$, where $n$ is the number of variables. Our proof of this bound is slightly simpler than one of Porschen, Randerath, and Speckenmeyer. These proofs are independent (and algorithms are slightly different), though they are based on the same ideas appeared in the proof of the previous bound $O(2^{0.186916n})$ by the same authors. 
@article{ZNSL_2002_293_a5,
     author = {A. S. Kulikov},
     title = {An upper bound $O(2^{0.16254n})$ for {Exact} {3-Satisfiability:} a simpler proof},
     journal = {Zapiski Nauchnykh Seminarov POMI},
     pages = {118--128},
     publisher = {mathdoc},
     volume = {293},
     year = {2002},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZNSL_2002_293_a5/}
}
TY  - JOUR
AU  - A. S. Kulikov
TI  - An upper bound $O(2^{0.16254n})$ for Exact 3-Satisfiability: a simpler proof
JO  - Zapiski Nauchnykh Seminarov POMI
PY  - 2002
SP  - 118
EP  - 128
VL  - 293
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/ZNSL_2002_293_a5/
LA  - ru
ID  - ZNSL_2002_293_a5
ER  - 
%0 Journal Article
%A A. S. Kulikov
%T An upper bound $O(2^{0.16254n})$ for Exact 3-Satisfiability: a simpler proof
%J Zapiski Nauchnykh Seminarov POMI
%D 2002
%P 118-128
%V 293
%I mathdoc
%U http://geodesic.mathdoc.fr/item/ZNSL_2002_293_a5/
%G ru
%F ZNSL_2002_293_a5
A. S. Kulikov. An upper bound $O(2^{0.16254n})$ for Exact 3-Satisfiability: a simpler proof. Zapiski Nauchnykh Seminarov POMI, Computational complexity theory. Part VII, Tome 293 (2002), pp. 118-128. http://geodesic.mathdoc.fr/item/ZNSL_2002_293_a5/