2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Dmytro Taranovsky Sep 21 '17 at 23:02
3
$\begingroup$

Yes, sliding blocks, Rush Hour, and many other puzzles with reversible moves are (deterministic) linear space complete. By contrast, many puzzles with irreversible moves, including Sokoban, are complete for nondeterministic linear space.

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

For appropriate board representations, we even have, for every problem in linear space, a deterministic finite state transducer that reduces instances to solvability of sliding blocks. The transducer gives an nxk board; if we want an mxm board, linear time logspace reductions remain sufficient.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.