New answers tagged

-2

Recently, I have presented a randomized algorithm for #$k$-SAT which counts the exact number of satisfying assignments in $2^{o(n)}$ time (and linear space), thereby refuting #ETH and related hypotheses: The #ETH is False, #k-SAT is in Sub-Exponential Time The crucial insight is: count without search. The algorithm counts all satisfying assignments without ...


7

There are several #k-SAT algorithms in the literature which can beat $2^n$. Here is a randomized one that gets $2^{n(1-1/O(k))}$ time (like PPSZ): https://cseweb.ucsd.edu/~paturi/myPapers/pubs/ImpagliazzoMatthewsPaturi_2012_soda.pdf There is also a deterministic algorithm with $2^{n(1-1/O(k))}$ runtime behavior. Here is a link: http://tmc.web.engr.illinois....


Top 50 recent answers are included