1 citations · 2 across the 12 of their papers we have counts for
Showing cs.CCShow all
2 papers · 1 filter
cs.CC2025
Pushing Blocks without Fixed Walls via Checkable Gizmos: Push-1 is PSPACE-Complete
MIT Hardness Group, Josh Brunner, Lily Chung +4
We prove PSPACE-completeness of Push-1: given a rectangular grid of 1 x 1 cells, each possibly occupied by a movable block, can a robot move from one specified location to another,…
cs.CC2025
#P is Sandwiched by One and Two #2DNF Calls: Is Subtraction Stronger Than We Thought?
Max Bannach, Erik D. Demaine, Timothy Gomez +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)…