文章基本信息

标题：Algorithms for SAT and Upper Bounds on Their Complexity
本地全文：下载
作者：Evgeny Dantsin ; Edward Hirsch ; Sergei Ivanov 等
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2001
卷号：2001
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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".
关键词：derandomization , propositional satisfiability , worst-case upper bounds