# complexity of Sokoban with a small number of boxes

(I asked a very concise version of this one month ago on cs.stackexchange,
and although it got edited, it was not (otherwise) responded to.)

In this post, for positive integer values $k$, "$k$-Sokoban" is simply short for
"the problem "Given an instance of Sokoban with at most $k$ boxes, is that instance solvable?"".
For any particular encoding, that is one problem for which complexities should be expressed
in terms of both $k$ and $n$ (like how the complexity of graph algorithms is frequently
expressed in terms of both $|V\hspace{.02 in}|$ and $|\hspace{.02 in}E\hspace{.03 in}|\hspace{-0.02 in}$), rather than a different problem for each value of $k$.
(Since one could just add inaccessible squares with a box already at its storage location,
"at most" can be replaced with "exactly" as long as $n$ can be increased sufficiently.)
This post has one part on upper bounds for the hardness of $k$-Sokoban,
one part on lower bounds for the hardness of $k$-Sokoban, and
one part on the plausibility of $k$-Sokoban being in a specific class.

Although these questions are complicated, that is just to expand the space of
possible answers to them. $\:$ I could simplify them, but that would make them harder.

By this paper, standard Sokoban can "easily" (i.e., via conversions of low complexity) emulate a non-deterministic LBA with the size increase and slowdown factors bounded by a polynomial
in the number of states per cell. $\:$ (The three places on pages 7 and 9 where it says "Select Next State" show the non-deterministic part, even thought the paper doesn't explicitly claim that.)
On the other hand, instances of $k$-Sokoban with size $n$ have $n^{\hspace{.02 in}O\hspace{.02 in}(k)}$ possible states and
one can easily work with those states, so $k$-Sokoban is in NSPACE$[\hspace{-0.02 in}O\hspace{.02 in}(k\hspace{-0.04 in}\cdot \hspace{-0.04 in}\log(n))] \;$.
Note that any way to solve $O(k)$-Sokoban with just resources of somewhat standard types
that are not known to be able to decide all of $\:\operatorname{NSPACE}\hspace{.02 in}[k\hspace{-0.04 in}\cdot \hspace{-0.04 in}\log(n)]\:$
would constitute an obstruction in the sense of my upper bound question.

As a broad example of that, I'm not aware of any way to show that for each
positive real number $\epsilon$, each (parameterized) language in $\:\operatorname{NSPACE}[\hspace{-0.02 in}O\hspace{.02 in}(k\hspace{-0.04 in}\cdot \hspace{-0.04 in}\log(n))]$
can infinitely-often be decided by the version of $\;$S$_{\hspace{.02 in}2}$nonuniformTISP$\left[n^{\hspace{.02 in}k^2\hspace{-0.02 in}\cdot o(\log(n))}\hspace{-0.05 in},\hspace{-0.02 in}n^{\hspace{.02 in}o(k)}\hspace{-0.04 in}\right]$
in which [whichever of $y,\hspace{-0.02 in}z$ is required to exist] can be chosen to have length $n^{\hspace{.02 in}o(k)}\hspace{-0.04 in}$
but the referee has (read-only) random access to $\:2^{\lceil n\text{^}\epsilon \hspace{-0.02 in}\rceil}\:$ bits of advice.

The Upper Bound Question:

Is there any obstruction to $O(k)$-Sokoban with size $poly(n)$ being "easily"
(i.e., via conversions of low complexity) able to emulate non-deterministic
Turing machines with $\:k\hspace{-0.04 in}\cdot \hspace{-0.04 in}\log(n)\:$ bits of workspace such that the size increase and
slowdown factors are still bounded by a polynomial in the number of states per cell?

(Other sorts of "obstruction"s would be the existence of such emulation procedures implying
a containment or non-containment or that a problem does or doesn't reduce to its complement,
where there is no known way to show the right-hand-side of the implication unconditionally.
Essentially, such an obstruction could be any argument for why it should be
difficult to prove the existence of such emulation procedures that is significantly
better than "$k$-Sokoban does not appear to support suitable gadgets".)

Let "MiTCGG" be short for "the problem "Is there a matching from one given set of $k$ vertices
to another given set of $k$ vertices in the transitive closure of the given directed grid graph?"".
(Those letters stand for "Matching in the Transitive Closure of a Grid Graph".) $\:$ Since the region

X    X
X XX XX
X  X  X
XX    X
XXX


has neither boxes nor storage locations and is such that a box can be pushed from the top
to exit out the bottom but can't be pushed from the bottom to the top, MiTCGG can easily
be reduced to $k$-Sokoban. $\;\;\;$ By this paper, the $\: k=1 \:$ version of MiTCGG is hard for NC1.
Additionally, the nLBA emulation result for standard Sokoban that I cited
earlier in this post will give useful lower bounds when $k$ is large enough.
Thus, $1$-Sokoban (so in particular $k$-Sokoban) is NC1-hard and instances of $O(k)$-Sokoban
with size $O(k)$ can "easily" (i.e., via conversions of low complexity) emulate NSPACE(k).

The Lower Bound Question:

Are there any hardness results for the search version of $k$-Sokoban
which do not automatically follow from the hardness results
everything in NC1 $\: \leq \:$ directed Grid Graph reachability $\: \leq \:$ MiTCGG $\: \leq \:$ $k$-Sokoban
and the fact that instances of $O(k)$-Sokoban with size $O(k)$ can
"easily" (i.e., via conversions of low complexity) emulate NSPACE(k)?

A 2-worktape non-deterministic Turing machine can solve MiTCGG in a way that uses
at most $O(\log(n))$ bits on one work tape and at most $k$ bits on the other work tape.
(Sketch: iterate over the $k$ starting points in order, guess directed paths to currently
unused finishing points, and keep track of which finishing points have been used so far.)

The Class Membership Question:

Is there any obstruction to $k$-Sokoban being solvable by a 2-worktape
non-deterministic Turing machine that uses $\:O\hspace{.02 in}(\log(n))\:$ bits
on one work tape and at most $k$ bits on the other work tape?

• Probably I misunderstood your question, but for what regards the class membership question, for fixed $k$ $O(\log(n)) = O (2k\log(n))$ and $2k\log(n)$ space is enough for keeping track of the positions of all the $k$ moveable barrels (the only moveable elements in the game) in an $n \times n$ board. So at every step you can non-deterministically pick and move a barrel (if it can be moved) and check if the board is solved. Apr 29 '15 at 6:45
• Thus, any obstruction regarding the class membership question can't fix $k$. $\:$ In other words, your observation very slightly supports the hypothesis that there is an algorithm satisfying the conditions I described in the class membership question. $\:$ Any significant support for that hypothesis (about $k$-Sokoban as defined at the top of my post, rather than with fixed $k$) would constitute an obstruction in the sense of my upper bound question. $\;\;\;\;$
– user6973
Apr 29 '15 at 10:06
• What are exactly "the conditions I described in the class membership question"? In the class membership question you allow nondeterminism, so the simple "guess-a-move algorithm" should solve k-Sokoban using $(k+1)\log n \in O(\log(n)$ space on a single work tape. (probably I still don't grasp the obstruction concept) Apr 29 '15 at 10:59
• "the conditions I described in the class membership question" are "2-worktape"s and "non-deterministic" and "uses $\:O\hspace{.02 in}(\log(n))\:$ bits on one work tape and at most $k$ bits on the other work tape". $\;\;\;$ $k$ is not constant (and not $O(1)$), so your suggestion uses more than $\:O(\log(n))\:$ space on its work tape. $\;\;\;\;\;\;\;\;$
– user6973
Apr 29 '15 at 11:07
• If $k$ is not a constant, then I'm probably missing the difference between Sokoban and $k$-Sokoban: e.g. 2-Sokoban is the set of Sokoban problems restricted to 2 boxes. For any k $k$-Sokoban can be solved non-deterministically in $O(\log n)$ space. If you consider the union of all $k$-Sokoban problems (for all $k$) then you're no more talking about $k$-Sokoban, but about Sokoban. In other words what are the valid inputs on the input tape (in your membership question)? Apr 29 '15 at 11:24