I have found this challenge and now I'm interested how hard it is being generalized.

It can be reformulated like this:

Given numbers $N,k$ find a if there exists string of directions (W,E,N,S) that will reach every reachable cell on every $N\times N$ grid from any position of length at most $k$.

We only need to find a string that will pass all $N^2$ cells from any position on following grids:

  1. Number of walls is $(N-1)^2$.
  2. Every cell is reachable.

It appears that number of such grids is exponential on $N$. So, the solution can be checked in 2-exponential time. Hm, for $2\times 2$ there only are 4 such grids,for $3\times 3$ there are 189 such grids. Perhaps, this problem is even harder.

But is this problem $\mathsf{NEXP}$-complete? If so, this would be one of the most natural $\mathsf{NEXP}$-complete problems.

Of course it is possible that shortest string can be expressed using some formula. Since I suspect that this string depends at most exponentially on $N$, it would be in $\mathsf{EXP}$.

  • $\begingroup$ How is the input given? If $N,k$ are given in unary then the problem has a simple PSPACE solution, and consequently is probably not NEXP-complete. $\endgroup$ – Ariel Sep 15 '17 at 21:55
  • $\begingroup$ The trivial way to check if a path is universal requires exponential time in $N$, so even when $N,k$ are given in unary, the trivial solution does not put your problem in NP. If $N$ is given in binary, the trivial solution is actually double exponential. $\endgroup$ – Ariel Sep 15 '17 at 22:01
  • $\begingroup$ @Ariel, $\mathsf{EXPSPACE}$-complete then? $\endgroup$ – rus9384 Sep 15 '17 at 22:03
  • $\begingroup$ It's your question, so I don't know. Actually for unary encoding this problem is in $\Sigma_2$. $\endgroup$ – Ariel Sep 15 '17 at 22:16
  • $\begingroup$ You might want to look up universal traversal sequences. The existence of $n^{O(\log n)}$ length universal traversal sequence for 4-regular graphs (see this pdfs.semanticscholar.org/b038/…) implies there exists an $n^{O(\log n)}$ length sequence for your mazes, though there are probably shorter sequences since you're dealing with a very specific class of graphs (the result in the paper is about arbitrary regular graphs). $\endgroup$ – Ariel Sep 15 '17 at 22:20

Your Answer

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

Browse other questions tagged or ask your own question.