Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR05-030 | 12th February 2005 00:00

An Improved Upper Bound for SAT

RSS-Feed




TR05-030
Authors: Evgeny Dantsin, Alexander Wolpert
Publication: 7th March 2005 16:56
Downloads: 1495
Keywords: 


Abstract:

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 and the number of clauses in the input formula. This bound is asymptotically better than the previously best known $2^{n(1-1/\log(2m))}$ bound for SAT.



ISSN 1433-8092 | Imprint