The FP-versus-symmetric subtraction conjecture for monotone 2SAT counting
The FP-versus-symmetric subtraction conjecture for monotone 2SAT counting
Let denote the counting problem that counts satisfying assignments of monotone 2SAT formulas, and let denote the class of functions computable with logarithmically many such oracle calls. Let denote the analogous class allowing an oracle together with logarithmically many monotone 2SAT counting calls, and let denote the class obtained from logarithmically many differences of monotone 2SAT counting calls.
FP-versus-symmetric subtraction conjecture. is strictly contained in .
The paper has established that logarithmically many symmetric differences of monotone 2SAT counting calls capture the relevant hardness of , while it leaves open whether one call can be replaced by an 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
Sign in to submit a solution.
No solutions have been posted yet.