Consider puzzles like Rush-Hour or Klotski. When suitably generalized, such puzzles are known to be PSPACE-complete, but surely there is an interesting subclass of instances intesecting NP (and not intesrsecting P).

I'm wondering whether there's an easy search-to-decision reduction for problems where the solution-path grows polynomially (but where, as decision problems, are presumably still hard). A little more formally, for all instances of Rush-Hour puzzles on $n\times n$ grids that have a shortest path of length no more than, say, $n^3$, given access to an oracle $A$ that decides whether there is a solution that gets the target car out of the jam, is there a polynomial-time algorithm to search for the sequence of moves to get the car out?

My secret motivation is whether a quantum walk could easily traverse the state space; but because quantum walks are often known to be "forgetful" of the path from which they came, such walks may not easily give the actual solution (even if they could find the exit quickly enough). If there's a polynomial time search-to-decision reduction then such forgetfulness would be no crime.

From this website of Michael Fogleman:

Rush Hour graph

The specific subclass of instances that I'd be interested in if it is non-empty, are those that (1) have a polynomially bounded solution path - thus the subclass is necessarily contained in NP, (2) can be found with a quantum walk that doesn't grow superpolynomially - thus the subclass is necessarily contained in BQP, and (3) are not efficient classically - thus the subclass is necessarily not contained in P or BPP. If the shortest path grows superpolynomially then I'm pretty sure even a quantum walk would grow superpolynomially as well.

  • $\begingroup$ That would be a well-specific question, but I have doubts about whether that's the right way to formalize the question you want to ask, because whether a grid falls into that class is not recognizable in $P$. $\endgroup$
    – D.W.
    Commented May 13 at 17:12
  • $\begingroup$ *intersecting is spelled wrong $\endgroup$
    – Mark S
    Commented May 18 at 15:30

1 Answer 1


Yes! As long as we can give the oracle a limit on the number of steps in a path, I think we can do it this way:

  • Set $k\leftarrow n^3$ and set $B\leftarrow B_0$, where $B_0$ is the initial configuration of the board.

  • For each configuration $B'$ reachable in one step from $B$, ask the oracle if $B'$ has an escape path of at most $k-1$ steps. For the first such configuration you find: print $B'$, set $B\leftarrow B'$, set $k\leftarrow k-1$, and repeat.

Any Rush-Hour board configuration has $O(n^3)$ possible next configurations:

  • there are at most $n^2$ cars.
  • each car can move to at most $n-1$ different positions in one step.
  • each step only moves one car.

This procedure therefore queries the oracle $O(n^3\times n^3)$ times.

  • 1
    $\begingroup$ Yeah pretty obvious now, especially when promised that the path is at most $n^3$ serving as the base for the induction. Thanks! $\endgroup$
    – Mark S
    Commented May 14 at 16:50

Your Answer

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

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