(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 forthe 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 expressedin terms of both $k$ and $n$ (like how the complexity of graph algorithms is frequentlyexpressed 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, andone part on the plausibility of $k$-Sokoban being in a specific class.Although these questions are complicated, that is just to expand the space ofpossible 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 polynomialin 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 andone 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 typesthat 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 eachpositive 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 obstructions would be the existence of such emulation procedures implyinga 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 bedifficult to prove the existence of such emulation procedures that is significantlybetter 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$ verticesto 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 regionX    XX XX XXX  X  XXX    X    XXXhas neither boxes nor storage locations and is such that a box can be pushed from the topto exit out the bottom but can't be pushed from the bottom to the top, MiTCGG can easilybe 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 citedearlier 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)$-Sokobanwith 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 usesat 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 currentlyunused 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?
complexity of Sokoban with a small number of boxes
space bounded;parameterized complexity;nondeterminism;puzzles