#P is Sandwiched by One and Two #2DNF Calls: Is Subtraction Stronger Than We Thought?
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909642366386176 |
|---|---|
| author | Bannach, Max Demaine, Erik D. Gomez, Timothy Hecher, Markus |
| author_facet | Bannach, Max Demaine, Erik D. Gomez, Timothy Hecher, Markus |
| contents | 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 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 $\not\subseteq$ 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 $\geq$ 3 and respective counting versions. We further show that both #2DNF calls can be combined into a single call if we allow a little postprocessing (computable by AC0- or TC0-circuits). Consequently, we derive refined versions of Toda's Theorem: PH $\subseteq$ [#MON2SAT]$^{log}_{TC0}$ = [#MON2DNF]$^{log}_{TC0}$ and PH $\subseteq$ [#IMPL2SAT]$^{log}_{AC0}$. 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_06716 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | #P is Sandwiched by One and Two #2DNF Calls: Is Subtraction Stronger Than We Thought? Bannach, Max Demaine, Erik D. Gomez, Timothy Hecher, Markus Computational Complexity Discrete Mathematics Data Structures and Algorithms Logic in Computer Science Combinatorics 68Q17, 68Q15, 68Q25, 68Q27, 03B05, 03D10, 03D15, 05C85, 05C62, 05-08, 94C15 G.2.1; G.2.2; F.4.1; F.1.3; F.1.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) 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 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 $\not\subseteq$ 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 $\geq$ 3 and respective counting versions. We further show that both #2DNF calls can be combined into a single call if we allow a little postprocessing (computable by AC0- or TC0-circuits). Consequently, we derive refined versions of Toda's Theorem: PH $\subseteq$ [#MON2SAT]$^{log}_{TC0}$ = [#MON2DNF]$^{log}_{TC0}$ and PH $\subseteq$ [#IMPL2SAT]$^{log}_{AC0}$. 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. |
| title | #P is Sandwiched by One and Two #2DNF Calls: Is Subtraction Stronger Than We Thought? |
| topic | Computational Complexity Discrete Mathematics Data Structures and Algorithms Logic in Computer Science Combinatorics 68Q17, 68Q15, 68Q25, 68Q27, 03B05, 03D10, 03D15, 05C85, 05C62, 05-08, 94C15 G.2.1; G.2.2; F.4.1; F.1.3; F.1.1 |
| url | https://arxiv.org/abs/2506.06716 |