Pushing Blocks without Fixed Walls via Checkable Gizmos: Push-1 is PSPACE-Complete
Pith reviewed 2026-05-18 21:18 UTC · model grok-4.3
The pith
A robot can reach its target by pushing one block at a time on a grid with only movable blocks if and only if the problem lies in PSPACE.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
We show that the Push-1 problem is PSPACE-complete. Push-1 asks if there is a sequence of moves and single-block pushes that takes the robot from its starting position to the target on a grid where every cell is either empty or holds a movable block. By removing the requirement for fixed walls that previous proofs needed, the result applies to more general settings. The proof introduces checkable gizmos that the robot traverses to enforce logical constraints during the reconfiguration of block positions.
What carries the argument
Checkable gizmos: arrangements of movable blocks that the robot can enter in specific ways to verify and transition between states, extending earlier gadget methods to work without fixed walls.
Load-bearing premise
A stronger auxiliary gadget exists that can perform the necessary checks and state enforcements using only movable blocks in the gizmo framework.
What would settle it
A specific grid configuration where the robot reaches the target through a sequence that bypasses a checkable gizmo's intended restriction would show the hardness reduction does not hold.
read the original abstract
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, given the ability to push up to one block at a time? In particular, we remove the need for fixed (immovable) walls from a 2022 result. This fundamental model of block pushing, introduced in 1999, abstracts the mechanics of many video games. It was shown NP-hard in 2000, but its final complexity remained open for 25 years. Our result uses a new framework for checkable gadgets/gizmos, extending a prior framework for checkable gadgets to handle reconfiguration problems, at the cost of requiring a stronger auxiliary gadget. We also introduce a new connection between the motion-planning-through-gadgets framework (with an agent) and the Graph Orientation Reconfiguration Problem (with no agent), including Nondeterministic Constraint Logic.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proves PSPACE-completeness of Push-1 (robot navigating a grid of movable 1x1 blocks by pushing at most one at a time, from start to target location) without any fixed walls. It extends a prior checkable-gadgets framework to 'checkable gizmos' for reconfiguration problems (at the cost of a stronger auxiliary gadget) and connects the agent-based motion-planning-through-gadgets model to the agent-free Graph Orientation Reconfiguration Problem / Nondeterministic Constraint Logic.
Significance. If the reduction holds, this resolves a 25-year open question on the complexity of this fundamental 1999 block-pushing model (NP-hard since 2000). The new gizmo framework and the explicit link between agent-based planning and reconfiguration problems are potentially reusable for other motion-planning hardness results.
major comments (2)
- [§4] §4 (Checkable Gizmos Framework): the stronger auxiliary gadget must be shown to be realizable using only movable 1x1 blocks while enforcing the required checkable traversal and state-transition properties under single-block pushes; any unintended sequence that bypasses a check or adds an extra degree of freedom would invalidate the NCL simulation.
- [§5] §5 (Reduction Construction): the composition of gizmos into a wall-free instance must be verified to faithfully simulate the NCL orientation constraints without post-hoc adjustments or leakage; the paper's claim that the framework extends prior work to reconfiguration rests on this step.
minor comments (2)
- [Introduction] Clarify the precise difference between 'gadget' and 'gizmo' in the introduction, as readers familiar with the 2022 checkable-gadgets paper may be confused by the terminology shift.
- [Figures] Add explicit captions or legends to all gadget diagrams indicating allowed push directions and reachable states.
Simulated Author's Rebuttal
We thank the referee for their thorough review and for recognizing the significance of resolving the long-standing open question on the complexity of Push-1. We address each major comment below with clarifications drawn from the manuscript and indicate planned revisions to improve clarity and verifiability.
read point-by-point responses
-
Referee: [§4] §4 (Checkable Gizmos Framework): the stronger auxiliary gadget must be shown to be realizable using only movable 1x1 blocks while enforcing the required checkable traversal and state-transition properties under single-block pushes; any unintended sequence that bypasses a check or adds an extra degree of freedom would invalidate the NCL simulation.
Authors: Section 4 explicitly constructs the stronger auxiliary gadget from movable 1x1 blocks alone. The construction is accompanied by a case analysis of all single-block push sequences, demonstrating that traversals either follow the prescribed checkable paths (updating the internal state correctly) or are mechanically blocked by the geometry of the blocks. No sequence permits bypassing the check or introducing extraneous degrees of freedom, as any deviation collides with an adjacent block that cannot be pushed without violating the single-push rule. We will add an explicit figure of the gadget and an appendix enumerating the push sequences to make the verification more immediate for readers. revision: partial
-
Referee: [§5] §5 (Reduction Construction): the composition of gizmos into a wall-free instance must be verified to faithfully simulate the NCL orientation constraints without post-hoc adjustments or leakage; the paper's claim that the framework extends prior work to reconfiguration rests on this step.
Authors: Section 5 assembles the gizmos into a rectangular grid using only movable blocks, with the auxiliary gadget providing the necessary separation between components. Because each gizmo is checkable, any attempt to leak information or reconfigure across boundaries requires a traversal that the check mechanism forbids; the overall configuration therefore simulates the NCL orientation constraints exactly. The reduction does not rely on post-hoc adjustments. To strengthen the presentation we will insert a short proof sketch in the revised manuscript showing that the composition preserves the NCL semantics without unintended interactions. revision: yes
Circularity Check
Minor self-citation for gadget framework extension; central reduction from independent NCL remains non-circular
full rationale
The derivation reduces Push-1 PSPACE-completeness to Nondeterministic Constraint Logic (NCL), an externally established PSPACE-complete problem from prior literature. The checkable-gizmos framework is explicitly described as an extension of earlier checkable-gadgets work rather than a self-referential definition. No load-bearing step reduces by construction to a fitted parameter, self-citation chain, or ansatz smuggled from the same authors' unverified prior result. The auxiliary gadget is presented as a new construction whose correctness is argued directly in the paper, not presupposed by citation. This yields a self-contained reduction against an external benchmark, consistent with a low circularity score.
Axiom & Free-Parameter Ledger
axioms (2)
- standard math Nondeterministic Constraint Logic is PSPACE-complete.
- domain assumption The motion-planning-through-gadgets framework can be connected to Graph Orientation Reconfiguration.
invented entities (1)
-
Checkable gizmos
no independent evidence
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.