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

From papers

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.

Progress summary

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

Sources & referencesView supporting material

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).

Solutions 0

No solutions have been posted yet.