Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FUN.2018.19
URN: urn:nbn:de:0030-drops-88104
URL: https://drops.dagstuhl.de/opus/volltexte/2018/8810/
Demaine, Erik D. ; Lockhart, Joshua ; Lynch, Jayson
The Computational Complexity of Portal and Other 3D Video Games
| pdf-format: |
|
Abstract
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].
BibTeX - Entry
@InProceedings{demaine_et_al:LIPIcs:2018:8810,
author = {Erik D. Demaine and Joshua Lockhart and Jayson Lynch},
title = {{The Computational Complexity of Portal and Other 3D Video Games}},
booktitle = {9th International Conference on Fun with Algorithms (FUN 2018)},
pages = {19:1--19:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-067-5},
ISSN = {1868-8969},
year = {2018},
volume = {100},
editor = {Hiro Ito and Stefano Leonardi and Linda Pagli and Giuseppe Prencipe},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8810},
URN = {urn:nbn:de:0030-drops-88104},
doi = {10.4230/LIPIcs.FUN.2018.19},
annote = {Keywords: video games, hardness, motion planning, NP, PSPACE}
}
| Keywords: | video games, hardness, motion planning, NP, PSPACE | |
| Seminar: | 9th International Conference on Fun with Algorithms (FUN 2018) | |
| Issue date: | 2018 | |
| Date of publication: | 04.06.2018 |
