Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > UPPER BOUNDS FOR SATISFIABILITY-TESTING ALGORITHMS:
Reports tagged with upper bounds for satisfiability-testing algorithms:
TR04-017 | 22nd February 2004
Evgeny Dantsin, Alexander Wolpert

Derandomization of Schuler's Algorithm for SAT

Recently Schuler \cite{Sch03} presented a randomized algorithm that
solves SAT in expected time at most $2^{n(1-1/\log_2(2m))}$ up to a
polynomial factor, where $n$ and $m$ are, respectively, the number of
variables and the number of clauses in the input formula. This bound
is the best known ... more >>>


TR05-102 | 13th September 2005
Evgeny Dantsin, Edward Hirsch, Alexander Wolpert

Clause Shortening Combined with Pruning Yields a New Upper Bound for Deterministic SAT Algorithms

We give a deterministic algorithm for testing satisfiability of formulas in conjunctive normal form with no restriction on clause length. Its upper bound on the worst-case running time matches the best known upper bound for randomized satisfiability-testing algorithms [Dantsin and Wolpert, SAT 2005]. In comparison with the randomized algorithm in ... more >>>




ISSN 1433-8092 | Imprint