|
Zapiski Nauchnykh Seminarov POMI, 2001, Volume 277, Pages 14–46
(Mi znsl1427)
|
|
|
|
This article is cited in 12 scientific papers (total in 12 papers)
Algorithms for SAT and upper bounds on their complexity
M. A. Vsemirnov, E. A. Hirsch, E. Ya. Dantsin, S. V. Ivanov St. Petersburg Department of V. A. Steklov Institute of Mathematics, Russian Academy of Sciences
Abstract:
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”.
Received: 15.01.2001
Citation:
M. A. Vsemirnov, E. A. Hirsch, E. Ya. Dantsin, S. V. Ivanov, “Algorithms for SAT and upper bounds on their complexity”, Computational complexity theory. Part VI, Zap. Nauchn. Sem. POMI, 277, POMI, St. Petersburg, 2001, 14–46; J. Math. Sci. (N. Y.), 118:2 (2003), 4948–4962
Linking options:
https://www.mathnet.ru/eng/znsl1427 https://www.mathnet.ru/eng/znsl/v277/p14
|
Statistics & downloads: |
Abstract page: | 576 | Full-text PDF : | 297 |
|