Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Boolean satisfiability:
TR03-072 | 15th September 2003
Evgeny Dantsin, Edward Hirsch, Alexander Wolpert

Algorithms for SAT based on search in Hamming balls

We present a simple randomized algorithm for SAT and prove an upper
bound on its running time. Given a Boolean formula F in conjunctive
normal form, the algorithm finds a satisfying assignment for F
(if any) by repeating the following: Choose an assignment A at
random and ... more >>>

TR05-030 | 12th February 2005
Evgeny Dantsin, Alexander Wolpert

An Improved Upper Bound for SAT

We give a randomized algorithm for testing satisfiability of Boolean formulas in conjunctive normal form with no restriction on clause length. Its running time is at most $2^{n(1-1/\alpha)}$ up to a polynomial factor, where $\alpha = \ln(m/n) + O(\ln \ln m)$ and $n$, $m$ are respectively the number of variables ... more >>>

ISSN 1433-8092 | Imprint