#P is Sandwiched by One and Two #2DNF Calls: Is Subtraction Stronger Than We Thought?

Max Bannach, Erik D. Demaine, Timothy Gomez +1

The canonical class in the realm of counting complexity is #P. It is well known that the problem of counting the models of a propositional formula in disjunctive normal form (#DNF)…