2026-07-27T17:10:51Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8810 2024-03-12T12:02:09Z ddc:004 open_access

The Computational Complexity of Portal and Other 3D Video Games Demaine, Erik D. Lockhart, Joshua Lynch, Jayson video games hardness motion planning NP PSPACE We classify the computational complexity of the popular video games Portal and Portal 2. We isolate individual mechanics of the game and prove NP-hardness, PSPACE-completeness, or pseudo-polynomiality depending on the specific game mechanics allowed. One of our proofs generalizes to prove NP-hardness of many other video games such as Half-Life 2, Halo, Doom, Elder Scrolls, Fallout, Grand Theft Auto, Left 4 Dead, Mass Effect, Deus Ex, Metal Gear Solid, and Resident Evil. These results build on the established literature on the complexity of video games [Aloupis et al., 2014][Cormode, 2004][Forisek, 2010][Viglietta, 2014]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Erik D. Demaine and Joshua Lockhart and Jayson Lynch 2018 Is Part Of LIPIcs, Volume 100, 9th International Conference on Fun with Algorithms (FUN 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FUN.2018.19 urn:nbn:de:0030-drops-88104 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2018.19 eng https://creativecommons.org/licenses/by/3.0/legalcode