Complexity of reachability in fractal mazes with traps

Question

Is reachability in fractal mazes with traps EXPTIME complete?

A fractal maze includes one or more copies of itself. For example, see the question Decidability of Fractal Maze or Puzzling StackExchange question Alice and the Fractal Hedge Maze.

In this question, a trap, when stepped on, destroys a maze passage, i.e. if we reach a given vertex (alt. edge), a given edge (if present) is permanently removed from the graph; allowing multiple traps in one location does not change the problem. In a fractal maze, maze copies also copy traps (with trap activation on a per-copy basis). We allow directed edges, but because of traps, that does not matter for the question.

Posted in Q/A format as I was able to answer it while writing out related results, but I welcome other answers, including additional details, tighter bounds, similar questions/variations, and whether computational complexity of fractal mazes has been studied before.

Variations: A restriction is to require the maze to be planar. A strengthening of reachability is to allow reachability infinitely often (this has subtle dynamics), and with a further strengthening requiring the path to be reusable; for these strengthenings, a variation is to disallow directed edges.

Some reachability results

Reachability in undirected graphs is LOGSPACE complete.
Reachability in directed graphs is NL complete; it is open (as of 2022) whether this holds for planar directed graphs.
Reachability in undirected mazes with noncomsumable keys (that open doors) is P complete.
Reachability in mazes with traps, or with consumable keys (I think even if every door works with every key, consuming one key), or with directed paths with nonconsumable keys (or all three) is NP complete.
Reachability in mazes with switches (that toggle some edges) is PSPACE complete.

Reachability in fractal mazes (directed or not) is P complete. To see this, let $C(i,j)$ hold iff exit $i$ is reachable from exit $j$. Then the maze gives a monotonic recursive relation for $C$, and the true $C$ is its least fixed point. (As an aside, taking the greatest fixed point (which is also P complete) corresponds to connectivity when at high enough depth (or in a sense in the limit) we can tunnel through the walls of the submaze.) In the other direction, we can use the reachability to simulate a monotonic circuit. Also, for fractal mazes with $O(\sqrt{\log n})$ (external) exits, reachability is in NL, and LOGSPACE (aka L) for undirected mazes.

Despite being in P, reaching an exit in a fractal maze can take an exponential number of moves, but the maximum depth is polynomial, and the directions can be printed by a (deterministic) PDA having polynomially many internal states.

Reachability in fractal mazes with switches is undecidable, even if the maze directly contains only one copy of itself, each copy directly contains only a single switch, and each switch can be toggled only once. This holds because Turing machines with a single write-once binary tape (i.e. 1→0 is disallowed) are Turing complete as we can repeatedly copy the work area.

Answer 1

Reachability in fractal mazes with traps is EXPTIME complete. The maximum shortest path length is $2^{2^{n^{Θ(1)}}}$.

Reachability in fractal mazes with traps is in EXPTIME (and in PSPACE if the maze directly contains only one copy of itself) since it can be reduced to the following game. Player 1 draws the path except for portions in the maze copies, but including the ordering of the segments, then player 2 chooses a copy, and the players recurse, with player 1 winning once the paths in the copy do not enter its subcopies (and there are no inconsistencies).

In the other direction, we use a maze based on the configuration graph of a chosen nondeterministic Turing machine with $O(\log n)$ internal memory (and thus $n^{O(1)}$ maze size) that includes head position(s), and a binary tape of length $n^{Θ(1)}$ encoded by traps. Each bit, once written, is encoded by a pair of traps (allowing a trap to have multiple trigger points and affect multiple edges) exactly one of which was activated. We always write bits in new locations. Entering a maze copy corresponds to a 'recurse' ability (and hence PSPACE hardness) while having two direct maze subcopies captures alternating PSPACE, which equals EXPTIME. Also, just one trap (with multiple triggers and affecting multiple edges, and with the maze having directed edges) per copy suffices.

I am not sure about complexity of reachability in fractal mazes with anti-traps (that add rather than remove edges).

It is undecidable whether given a fractal maze with traps and an initial position, it is possible to get stuck (making escape impossible), even if the maze directly includes only one copy of itself and there are no directed edges. This is shown using a trap array copying construction such that the copying must be done in order, and skipping an input or output index permanently leaves an escape hatch.

Extension with linked switches

Reachability in fractal mazes with switches that are linked across copies (thus avoiding per-copy state) is EXPTIME complete. Using such switches, one can emulate a maze of exponential size, and conversely. The presence of exponentially many direct subcopies (if desired) can be emulated using depth $n$ subcopies.

Reachability in fractal mazes with linked switches and per-copy traps (traps always use different edges from switches) is 2-EXPTIME complete, with the maximum shortest path length 2^2^2^n^Θ(1). If the maze directly includes just one copy of itself, reachability EXPSPACE complete. The completeness should also apply to mazes without directed edges, but I did not verify it (this is nontrivial since we traverse the same edges multiple times here).

The completeness holds because using linked switches we can simulate an exponentially larger maze (and conversely), which can then be combined with the above EXPTIME treatment of traps (PSPACE if there is just one direct copy).

It appears to be 3-EXPTIME complete (and with maximum shortest path length 2^2^2^2^n^Θ(1)) whether without stepping on the same location twice (but your pursuer can), you can become unreachable (alt. make a given exit unreachable) from a given exit in a fractal maze with linked switches and per-copy traps. Linked switches may require your pursuer to enter a copy 2^n^Θ(1) times, with 2^2^n^Θ(1) entry-exit possibilities (controlled using traps), and thus 2^2^n^Θ(1) bits to encode permitted possibilities, corresponding to 2^2^2^n^Θ(1) game length, and before memoization, 2^2^2^2^n^Θ(1) game tree size. (In the game, player 1 draws path (except for subcopies) and for each direct subcopy it enters, permitted opponent entry-exit patterns, while player 2 chooses copy to recurse.)