Séminaire de Markus Hecher
#P is Sandwiched by One and Two #2DNF Calls: Is Subtraction Stronger Than We Thought?
23 oct. 2025 - 14:00The 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 is in SpanL which is strictly contained in #P under parsimonious reductions and reasonable assumptions. Hence, the class of functions logspace reducible to #DNF is a strict subset of #P under plausible complexity-theoretic assumptions. We show that, in contrast, two calls to a (restricted) #2DNF oracle are sufficient to capture GapP, that is, the logspace many-one closure of the difference between the results of two #2DNF calls is GapP. Since #P is strictly contained in GapP in this model, #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. It turns out that a single subtraction is sufficient 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. Our route to these results is via structure-preserving reductions that preserve parameters like treewidth up to an additive overhead. The absence of multiplicative overhead immediately yields parameterized SETH-tight lower bounds for counting.