Paper by Erik D. 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
- The paper is available in PDF (172k).
- See information on file formats.
- [Google Scholar search]
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated September 18, 2020 by