The complexity of Dyson Telescopes

Summary

Abstract. We give a PSPACE-completeness reduction from QBF (quantified Boolean formulas) to the Dyson Telescopes puzzle where opposing telescopes can overlap in at least two spaces. The reduction does not use tail ends of telescopes or initially partially extended telescopes. If two opposing telescopes can overlap in at most one space, we can solve the puzzle in polynomial time by a reduction to graph reachability.

Introduction

The complexity of many motion-planning problems has been studied extensively in the literature. This work has recently focused on very simple combinatorial puzzles (one-player games) that nonetheless exhibit the theoretical difficulty of general motion planning; see, e.g.,. Two main examples of this pursuit are a suite of pushing-block puzzles, culminating in, and a suite of problems involving sliding-block puzzles. In pushing-block puzzles, an agent must navigate an environment and push blocks in order to reach a goal configuration, while avoiding collisions. The variations of pushing blocks began with several versions that appeared in video games (the most classic being Sokoban), and continued to consider simpler and simpler puzzles with the goal of finding a polynomially solvable puzzle. Nonetheless, all reasonable pushing-block puzzles turned out to be NP-hard, and many turned out to be PSPACE-complete, with no problems known to be in NP, except in one trivial case where solution paths are forced to be short. Similarly, sliding-block puzzles are usually PSPACE-complete, even in very simple models.