Paper by Erik D. Demaine

Reference:

Jeffrey Bosboom, Erik D. Demaine, Adam Hesterberg, Jayson Lynch, and Erik Waingarten, “Mario Kart is Hard”, in Revised Papers from the 18th Japan Conference on Discrete and Computational Geometry and Graphs (JCDCGG 2015), Lecture Notes in Computer Science, volume 9943, Kyoto, Japan, September 14–16, 2015, pages 49–59.

Abstract:

Nintendo's Mario Kart is perhaps the most popular racing video game franchise. Players race alone or against opponents to finish in the fastest time possible. Players can also use items to attack and defend from other racers. We prove two hardness results for generalized Mario Kart: deciding whether a driver can finish a course alone in some given time is NP-hard, and deciding whether a player can beat an opponent in a race is PSPACE-hard.

Comments:

This paper is also available from SpringerLink.

Availability:

The paper is available in PDF (9069k).

See information on file formats.

[Google Scholar search]

Related papers:

MarioKart_JCDCGG2015 (Mario Kart is Hard)