一句话：证明两次（或一次加后处理）#2DNF 调用的减法即可刻画 gapP，从而把 #P 严格夹在一次与两次调用之间。
本文研究计数复杂度中 #P 与 #DNF/#2DNF 的归约能力。已有结果将 #DNF 置于 spanL，#P 则可由 #DNF 的 Turing 归约刻画。作者证明：两次受限 #2DNF 查询结果相减，其 logspace many-one 闭包恰好是 gapP；因而 #P 被严格夹在一次与两次 #2DNF oracle 调用之间。进一步表明，若允许由 AC0 或 TC0 电路完成少量后处理，单次调用也可达到类似刻画，并推广到 #2SAT 与 #2DNF 的单调片段。归约是线性时间且保持结构性质，故可推出两者稀疏化引理、参数化 SETH 紧下界，以及精化版 Toda 定理 PH ⊆ [#MON2SAT]_{TC0}^{log} = [#MON2DNF]_{TC0}^{log}。
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 AC0-or TC0-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.
DOI 原文 ·
@inproceedings{paperbot8643,
title = {#P is Sandwiched by One and Two #2DNF Calls: Is Subtraction Stronger Than We Thought?},
author = {Max Bannach and Erik D. Demaine and Timothy Gomez and Markus Hecher},
booktitle = {LICS},
year = {2025},
doi = {10.1109/lics65433.2025.00010}
}