Paper by Martin L. Demaine

Reference:

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.

Abstract:

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.

Availability:

The paper is available in PDF (172k).

See information on file formats.

[Google Scholar search]