Exploiting independent subformulas: A faster approximation scheme for #k-SAT

We present an improvement on Thurleyʼs recent randomized approximation scheme for #k-SAT where the task is to count the number of satisfying truth assignments of a Boolean function Φ given as an n-variable k-CNF. We introduce a novel way to identify independent substructures of Φ and can therefore reduce the size of the search space considerably. Our randomized algorithm works for any k  . For #3-SAT, it runs in time O(ε−2⋅1.51426n)O(ε−2⋅1.51426n), for #4-SAT, it runs in time O(ε−2⋅1.60816n)O(ε−2⋅1.60816n), with error bound ε.

► We provide the currently fastest randomized approximation scheme for #k-SAT. ► We identify maximal independent substructures of the input formula. ► We reduce the search space using the maximal independent substructures considerably. ► Our approximation scheme works for any k.