5
$\begingroup$

Note: I have posted a hugely expanded version of this question on cstheory.

Since a Sokoban instance with only $k$ boxes has at most $n^{O(k)}$ possible states, the problem lies in $\operatorname{NSPACE}$$[O(k \cdot \log (n))]$. 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, 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?" can easily be reduced to the problem I am asking about.

Is anything else known about the complexity of Sokoban with only $k$ boxes?

In particular, is it the case that solvable instances always have solutions of length $n^{o(k)}$?

I tried to construct a bounded-counter gadget, but aside from realizing that such a gadget would require a box being moved along it when the counter's value is sufficiently large (since otherwise the player could just "pretend" to have incremented or decremented the counter), I wasn't able to get anywhere with that.

Improve this question
$\endgroup$
2
  • $\begingroup$ I didn't mean to sound that annoyed; I've toned down the intro (as you apparently noticed). $\:$ I personally like having spacing correspond somewhat with parsing, and otherwise in general making lines in the same paragraph have roughly the same lengths. $\;\;\;\;$ $\endgroup$
    – user12859
    Apr 9, 2015 at 21:25
  • 2
    $\begingroup$ I asked a question on Meta about formatting in general, see here. $\endgroup$
    – Juho
    Apr 9, 2015 at 21:45

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.