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

During the past three years there was an explosion of algorithms solving MAX-SAT and MAX-2-SAT in worst-case time of the order c^K, where c<2 is a constant, and K is the number of clauses in the input formula. Such bounds w.r.t. the number of variables instead of the number of ... 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 >>>