Zapiski Nauchnykh Seminarov POMI, Computational complexity theory. Part VI, Tome 277 (2001), pp. 14-46
Citer cet article
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/
@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},
year = {2001},
volume = {277},
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
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
%U http://geodesic.mathdoc.fr/item/ZNSL_2001_277_a1/
%G ru
%F ZNSL_2001_277_a1
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”.
