论文标题
长，短和随机
The Long, the Short and the Random
论文作者
论文摘要
我们提供了理论和经验的可靠证据，用于存在用于随机稀疏$ \＃ω（\ log n）$ - SAT实例的确定性算法，该实例计算了子指数时间中满足分配的确切计数。该算法使用每个CNF公式具有的不错的组合属性，该属性将其不满意分配的数量与单调子形式的空间联系起来。
We furnish solid evidence, both theoretical and empirical, towards the existence of a deterministic algorithm for random sparse $\#Ω(\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.
