Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > ALGORITHMS FOR SAT:
Reports tagged with algorithms for SAT:
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