researchers with a paper here

1 paper

cs.CC2012

The Relative Exponential Time Complexity of Approximate Counting Satisfying Assignments

Patrick Traxler

We study the exponential time complexity of approximate counting satisfying assignments of CNFs. We reduce the problem to deciding satisfiability of a CNF. Our reduction preserves…