ECCC-Report TR05-030https://eccc.weizmann.ac.il/report/2005/030Comments and Revisions published for TR05-030en-usMon, 07 Mar 2005 16:56:33 +0200
Paper TR05-030
| An Improved Upper Bound for SAT |
Evgeny Dantsin,
Alexander Wolpert
https://eccc.weizmann.ac.il/report/2005/030We 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.
Mon, 07 Mar 2005 16:56:33 +0200https://eccc.weizmann.ac.il/report/2005/030