Geodesic
Algorithms for SAT and upper bounds on their complexity
Zapiski Nauchnykh Seminarov POMI, Computational complexity theory. Part VI, Tome 277 (2001), pp. 14-46

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

We survey recent algorithms for the propositional satisfiability problem, in particular algorithms that have the best current worst-case upper bounds on their complexity. We also discuss some related issues: the derandomization of the algorithm of Paturi, Pudlák, Saks and Zane, the Valiant-Vazirani Lemma, and random walk algorithms with the “back button”. 
@article{ZNSL_2001_277_a1,
     author = {M. A. Vsemirnov and E. A. Hirsch and E. Ya. Dantsin and S. V. Ivanov},
     title = {Algorithms for {SAT} and upper bounds on their complexity},
     journal = {Zapiski Nauchnykh Seminarov POMI},
     pages = {14--46},
     publisher = {mathdoc},
     volume = {277},
     year = {2001},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZNSL_2001_277_a1/}
}
TY  - JOUR
AU  - M. A. Vsemirnov
AU  - E. A. Hirsch
AU  - E. Ya. Dantsin
AU  - S. V. Ivanov
TI  - Algorithms for SAT and upper bounds on their complexity
JO  - Zapiski Nauchnykh Seminarov POMI
PY  - 2001
SP  - 14
EP  - 46
VL  - 277
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/ZNSL_2001_277_a1/
LA  - ru
ID  - ZNSL_2001_277_a1
ER  - 
%0 Journal Article
%A M. A. Vsemirnov
%A E. A. Hirsch
%A E. Ya. Dantsin
%A S. V. Ivanov
%T Algorithms for SAT and upper bounds on their complexity
%J Zapiski Nauchnykh Seminarov POMI
%D 2001
%P 14-46
%V 277
%I mathdoc
%U http://geodesic.mathdoc.fr/item/ZNSL_2001_277_a1/
%G ru
%F ZNSL_2001_277_a1
M. A. Vsemirnov; E. A. Hirsch; E. Ya. Dantsin; S. V. Ivanov. Algorithms for SAT and upper bounds on their complexity. Zapiski Nauchnykh Seminarov POMI, Computational complexity theory. Part VI, Tome 277 (2001), pp. 14-46. http://geodesic.mathdoc.fr/item/ZNSL_2001_277_a1/