This is intended to be a simpler version of my earlier question here. In this post, 1-Sokoban-search is Sokoban with only 1 box, 1-Sokoban-decision is the corresponding decision problem, and 1-Sokoban refers to both of those problems. (You get to choose whether that also means there's only one storage location or still allows more storage locations. ​ Everything I say here applies in either case.) 1-Sokoban is trivially in NL. ​ Since, regardless of whether the ?s are X or blank, the region

?  X

will have no box and no storage location and be such that the box can be pushed from the top to exit out the right but can't be pushed from the right to the top, (directed) Grid Graph Reachability / (directed) GG search ​ ​ can easily be reduced to ​ 1-Sokoban-decision / 1-Sokoban-search ​ respectively, so 1-Sokoban is NC1-hard and not known to be solvable by L. Grid Graph distance is known to be in ​ UL ∩ coUL , ​ so by any search-to-value reduction, that is no obstacle to putting 1-Sokoban in ​ UL ∩ coUL . (However, I don't have any evidence for 1-Sokoban being in even LpromiseFewL.)

Is anything else known about 1-Sokoban?

In particular, I have been unable to come up with any decision-to-search reduction in which the search oracle incorrectly reporting "no solution" never causes false negatives / search-to-decision reduction by any slightly-"natural" class, even with a GGsearch oracle, that can't obviously already solve all of ​ NL / FNL ​respectively, and I've also been unable to come up with any evidence for or against hardness of 1-Sokoban, beyond the reduction from Grid Graphs.

  • $\begingroup$ Please stop breaking lines inside a paragraph manually. $\endgroup$
    – Kaveh
    Apr 9, 2016 at 19:14


Your Answer

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