Paper by Erik D. Demaine

Reference:

Jeffrey Bosboom, Josh Brunner, Michael Coulombe, Erik D. Demaine, Della H. Hendrickson, Jayson Lynch, and Elle Najt, “The Legend of Zelda: The Complexity of Mechanics”, Thai Journal of Mathematics, volume 21, number 4, December 2023, pages 687–716.

Abstract:

We analyze some of the many game mechanics available to Link in the classic Legend of Zelda series of video games. In each case, we prove that the generalized game with that mechanic is polynomial, NP-complete, NP-hard and in PSPACE, or PSPACE-complete. In the process we give an overview of many of the hardness proof techniques developed for video games over the past decade: the motion-planning-through-gadgets framework, the planar doors framework, the doors-and-buttons framework, the “Nintendo” platform game / SAT framework, and the collectible tokens and toll roads / Hamiltonicity framework.

Comments:

The paper is also available as arXiv:2203.17167 and from the journal.

Availability:

The paper is available in PDF (914k).

See information on file formats.

[Google Scholar search]

Related papers:

Zelda_TJCDCGGG2021 (The Legend of Zelda: The Complexity of Mechanics)