The Long, the Short and the Random

Abstract

We furnish solid evidence, both theoretical and empirical, towards the existence of a deterministic algorithm for random sparse $\#\Omega (\log n)$-SAT instances, which computes the exact counting of satisfying assignments in sub-exponential time. The algorithm uses a nice combinatorial property that every CNF formula has, which relates its number of unsatisfying assignments to the space of its monotone sub-formulae.

18 pages, 10 figures. Software implementation (in Java) available for download

Cited by in corpus (1)

• The #ETH is False, #k-SAT is in Sub-Exponential Time