DNF Sparsification and a Faster Deterministic Counting Algorithm
DNF Sparsification and a Faster Deterministic Counting Algorithm
We give a faster deterministic algorithm for approximately counting the number of satisfying solutions to a DNF or CNF. Given a DNF(or CNF) f on n variables and poly(n) terms, we give a deterministic n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Õ((log log n)</sup> <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">)</sup> time algorithm that computes …