Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with worst-case upper bounds:
TR99-036 | 6th September 1999
Edward Hirsch

A New Algorithm for MAX-2-SAT

Revisions: 2

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

TR00-019 | 20th March 2000
Edward Hirsch

Worst-case time bounds for MAX-k-SAT w.r.t. the number of variables using local search

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

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