ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR01-012 | 4th January 2001 00:00

Algorithms for SAT and Upper Bounds on Their Complexity

RSS-Feed

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, Pudlak, Saks and Zane, the Valiant-Vazirani
Lemma, and random walk algorithms with the "back button".



ISSN 1433-8092 | Imprint