Paper by Martin L. Demaine

Erik D. Demaine, Martin L. Demaine, Rudolf Fleischer, Robert A. Hearn, and Timo von Oertzen, “The Complexity of Dyson Telescopes”, in Games of No Chance 3, edited by Michael H. Albert and Richard J. Nowakowski, Mathematical Sciences Research Institute Publications, volume 56, 2009, pages 271–285, Cambridge University Press.

In this paper, we give a PSPACE-completeness reduction from QBF 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.

The paper is available in PDF (172k).
See information on file formats.
[Google Scholar search]

See also other papers by Martin Demaine.
These pages are generated automagically from a BibTeX file.
Last updated November 17, 2022 by Martin Demaine.