# Is sliding blocks linear space complete?

Sliding blocks is PSPACE complete even in its simplest form involving 1x2 and 2x1 blocks (without rotation or fractional positions) in a rectangular area, with goal being to move a designated block to the designated space. See "PSPACE-Completeness of Sliding-Block Puzzles and Other Problems through the Nondeterministic Constraint Logic Model of Computation" by Robert Hearn and Erik Demaine. However, that paper does not give a more precise characterization than PSPACE.

Is existence of a solution in sliding blocks (deterministic) linear space complete?

One choice of completeness is to use polynomial time linear space reductions with at most linear increase in instance size, but gadget based reductions also work in LOGSPACE and might even work in uniform linear size AC$^0$.

Offered using Q/A format.

• Let me know if I should be more explicit about the language {x: x is a solvable sliding blocks configuration}, or can otherwise enhance the exposition. – Dmytro Taranovsky Sep 21 '17 at 23:02

Sliding blocks is in linear space because the state has $O(n)$ bits and the moves are reversible (and undirected graph connectivity is in logspace).
In the other direction, the above paper first uses a reduction from nondeterministic constraint logic (NCL), and then reduces QBF to NCL. The NCL to sliding blocks reduction is space-efficient (at least if the wiring of NCL is based on a two dimensional grid of cells with $O(1)$ gates per cell, which suffices). However, even if the QBF to NCL reduction is efficient, known simulations of linear space use approximately quadratic size QBF.
Fortunately, a later paper offers a different reduction. "[Parameterized Complexity of Graph Constraint Logic]"(https://arxiv.org/abs/1509.02683) by Tom van der Zanden shows that NCL (even for bounded width corresponding to an nxk board) can simulate H-Word Reconfiguration (which can be used to simulate string rewriting with a finite set of reversible length-preserving rules). While the paper does not say it, H-Word Reconfiguration can be used for space-efficient (up to a constant factor) simulation of reversible Turing machines. In turn, given unbounded time, reversible Turing machines (as a computational model) are space-efficient. (However, it remains open whether some problems in $\mathrm{TimeSpace}(n^{O(1)}, O(n))$ take exponential time for linear space reversible Turing machines.)