Tootfinder

#P is Sandwiched by One and Two #2DNF Calls: Is Subtraction Stronger Than We Thought?
Max Bannach, Erik D. Demaine, Timothy Gomez, Markus Hecher
https://

#P is Sandwiched by One and Two #2DNF Calls: Is Subtraction Stronger Than We Thought?
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) is complete for #P under Turing reductions. On the other hand, #DNF $\in$ spanL and spanL $\not\subseteq$ #P unless NL = NP. Hence, the class of functions logspace-reducible to #DNF is a strict subset of #P under plausible complexity-theoretic assumptions. By contrast, we show that two calls to a (restricted) #2DNF o…