New answers tagged counting-complexity
-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
