#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 ∈ spanL and spanL ⊋ #P unless#DNFNL = NPis a strict. Hence, the class of functions logspace-reducible to subset of #P under plausible complexity-theoretic assumptions. By contrast, we show that two calls to a (restricted) #2DNF oracle suffice to capture gapP, namely, that the logspace many-one closure of the subtraction between the results of two #2DNF calls is gapP. Because #P ⊋ gapP, #P is strictly contained between one and two #2DNF oracle calls.Surprisingly, the propositional formulas needed in both calls are linear-time computable, and the reduction preserves interesting structural as well as symmetry properties, leading to algorithmic applications. We show that a single subtraction suffices to compensate for the absence of negation while still capturing gapP, i.e., our results carry over to the monotone fragments of #2SAT and #2DNF. Since our reduction is linear-time, it preserves sparsity and, as a consequence we obtain a sparsification lemma for both #2SAT and #2DNF. This has only been known for kSAT with k ≥ 3 and respective counting versions.We further show that both single call if we allow a little postprocessing (computable by AC<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">0</sup> -or TC<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">0</sup>-circuits). Consequently, we derive refined versions of Toda’s Theorem: ${\text{PH}} \subseteq [\# {\text{MON}}2{\text{SAT}}]_{{\text{T}}{{\text{C}}^0}}^{\log } = [\# {\text{MON}}2{\text{DNF}}]_{{\text{T}}{{\text{C}}^0}}^{\log }$. Our route to these results is via structure-aware reductions that preserve parameters like treewidth up to an additive overhead. The absence of multiplicative overhead indeed yields parameterized SETH-tight lower bounds.