The FP-versus-symmetric subtraction conjecture for monotone 2SAT counting

About 1 year old · traced to

Let \normalfont\textsc#mon2sat\text{\normalfont\textsc{\#mon2sat}} denote the counting problem that counts satisfying assignments of monotone 2SAT formulas, and let [\normalfont\textsc#mon2sat]log⁡[\text{\normalfont\textsc{\#mon2sat}}]^{\log} denote the class of functions computable with logarithmically many such oracle calls. Let [FP−\normalfont\textsc#mon2sat]log⁡[\mathrm{FP}-\text{\normalfont\textsc{\#mon2sat}}]^{\log} denote the analogous class allowing an FP\mathrm{FP} oracle together with logarithmically many monotone 2SAT counting calls, and let [\normalfont\textsc#mon2sat−\normalfont\textsc#mon2sat]log⁡[\text{\normalfont\textsc{\#mon2sat}}-\text{\normalfont\textsc{\#mon2sat}}]^{\log} denote the class obtained from logarithmically many differences of monotone 2SAT counting calls.

FP-versus-symmetric subtraction conjecture. [FP−\normalfont\textsc#mon2sat]log⁡[\mathrm{FP}-\text{\normalfont\textsc{\#mon2sat}}]^{\log} is strictly contained in [\normalfont\textsc#mon2sat−\normalfont\textsc#mon2sat]log⁡[\text{\normalfont\textsc{\#mon2sat}}-\text{\normalfont\textsc{\#mon2sat}}]^{\log}.

The paper has established that logarithmically many symmetric differences of monotone 2SAT counting calls capture the relevant hardness of gapP\mathrm{gap}\mathrm{P}, while it leaves open whether one call can be replaced by an FP\mathrm{FP} oracle. The authors expect that simulating negation by subtraction requires symmetry, which motivates the strict-containment conjecture.

References

Primary source

Max Bannach, Erik D. Demaine, Timothy Gomez and Markus Hecher, “#P is Sandwiched by One and Two #2DNF Calls: Is Subtraction Stronger Than We Thought?”, arXiv:2506.06716 (2025).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.