<p>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:</p>
<ul>
<li><p>Set <span class="math-container">$k\leftarrow n^3$</span> and set <span class="math-container">$B\leftarrow B_0$</span>, where <span class="math-container">$B_0$</span> is the initial configuration of the board.</p>
</li>
<li><p>For each configuration <span class="math-container">$B'$</span> reachable in one step from <span class="math-container">$B$</span>, ask the oracle if <span class="math-container">$B'$</span> has an escape path of at most <span class="math-container">$k-1$</span> steps. For the <em>first</em> such configuration you find: print <span class="math-container">$B'$</span>, set <span class="math-container">$B\leftarrow B'$</span>, set <span class="math-container">$k\leftarrow k-1$</span>, and repeat.</p>
</li>
</ul>
<p>Any Rush-Hour board configuration has <span class="math-container">$O(n^3)$</span> possible next configurations:</p>
<ul>
<li>there are at most <span class="math-container">$n^2$</span> cars.</li>
<li>each car can move to at most <span class="math-container">$n-1$</span> different positions in one step.</li>
<li>each step only moves one car.</li>
</ul>
<p>This procedure therefore queries the oracle <span class="math-container">$O(n^3\times n^3)$</span> times.</p>

CC BY-SA 4.0
2024-05-14T16:50:03.793Z
Yeah pretty obvious now, especially when promised that the path is at most $n^3$ serving as the base for the induction.

Thanks!
Mark S
CC BY-SA 4.0
2024-05-14T15:11:28.227Z
2024-05-14T15:11:28.227Z
wobtax
<p>Consider puzzles like <a href="https://en.wikipedia.org/wiki/Rush_Hour_(puzzle)" rel="nofollow noreferrer">Rush-Hour</a> or <a href="https://en.wikipedia.org/wiki/Klotski" rel="nofollow noreferrer">Klotski</a>. 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).</p>
<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 <span class="math-container">$n\times n$</span> grids that have a shortest path of length no more than, say, <span class="math-container">$n^3$</span>, <strong>given access to an oracle <span class="math-container">$A$</span> that <em>decides</em> whether there is a solution that gets the target car out of the jam, is there a polynomial-time algorithm to <em>search</em> for the sequence of moves to get the car out?</strong></p>
<p>My secret <a href="https://quantumcomputing.stackexchange.com/questions/38260/could-a-quantum-walk-easily-traverse-rush-hour-or-klotski-type-puzzles">motivation</a> is whether a quantum walk could easily traverse the state space; but because quantum walks are often <a href="https://arxiv.org/abs/2211.12447" rel="nofollow noreferrer">known</a> to be &quot;forgetful&quot; 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.</p>
<p>From <a href="https://www.michaelfogleman.com/rush/" rel="nofollow noreferrer">this website</a> of Michael Fogleman:</p>
<p><a href="https://i.sstatic.net/Zg87iBmS.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/Zg87iBmS.png" alt="Rush Hour graph" /></a></p>
<hr />
<p><sup> 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.</sup></p>

CC BY-SA 4.0
2024-05-13T17:12:23.530Z
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$.
D.W.
CC BY-SA 4.0
2024-05-18T15:30:38.113Z
*intersecting is spelled wrong
Mark S
<quantum-computing><pspace><puzzles>
Does Rush-Hour (or Klotski) admit a search-to-decision reduction?
Mark S
# Does Rush-Hour (or Klotski) admit a search-to-decision reduction?

(Asked by: username_0 on 2024-05-12)

Consider puzzles like [Rush-Hour](https://en.wikipedia.org/wiki/Rush_Hour_(puzzle)) or [Klotski](https://en.wikipedia.org/wiki/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](https://quantumcomputing.stackexchange.com/questions/38260/could-a-quantum-walk-easily-traverse-rush-hour-or-klotski-type-puzzles) is whether a quantum walk could easily traverse the state space; but because quantum walks are often [known](https://arxiv.org/abs/2211.12447) 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](https://www.michaelfogleman.com/rush/) of Michael Fogleman:

[![Rush Hour graph](https://i.sstatic.net/Zg87iBmS.png)](https://i.sstatic.net/Zg87iBmS.png)

---

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.

**Tags:** quantum-computing, pspace, puzzles
> **Comments:**
> **username_1**: 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$.  
> **username_0**: *intersecting is spelled wrong  

---

## 1 answers

### Answer by username_2 on 2024-05-14. Score: 4 | Accepted answer

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.

> **Comments:**
> **username_0**: Yeah pretty obvious now, especially when promised that the path is at most $n^3$ serving as the base for the induction.  Thanks!  

---

