Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Maxim Vsemirnov:

TR01-012 | 4th January 2001
Evgeny Dantsin, Edward Hirsch, Sergei Ivanov, Maxim Vsemirnov

Algorithms for SAT and Upper Bounds on Their Complexity

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 ... more >>>

ISSN 1433-8092 | Imprint