Recently there was a significant progress in proving (exponential-time) worst-case upper bounds for the propositional satisfiability problem (SAT). MAX-SAT is an important generalization of SAT. Several upper bounds were obtained for MAX-SAT and its NP-complete subproblems. In particular, Niedermeier and Rossmanith recently proved the worst-case upper bound O(2^{K/2.88...}) for MAX-2-SAT ... more >>>

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