An Improved Upper Bound for SAT

@techreport{citeulike:130909, 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.}, author = {Dantsin, Evgeny and Wolpert, Alexander }, citeulike-article-id = {130909}, howpublished = {ECCC Report TR05-030}, keywords = {sat}, posted-at = {2005-03-17 09:28:32}, priority = {2}, title = {An Improved Upper Bound for SAT} }

TY - RPRT ID - citeulike:130909 L3 - citeulike-article-id:130909 TI - An Improved Upper Bound for SAT N2 - 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. KW - sat AU - Dantsin, Evgeny AU - Wolpert, Alexander ER -