Paper by Erik D. Demaine

Reference:

Erik D. Demaine, Joshua Lockhart, and Jayson Lynch, “The Computational Complexity of Portal and Other 3D Video Games”, in Proceedings of the 9th International Conference on Fun with Algorithms (FUN 2018), La Maddalena, Italy, June 13–15, 2018, 19:1–19:22.

BibTeX

@InProceedings{Portal_FUN2018,
  AUTHOR        = {Erik D. Demaine and Joshua Lockhart and Jayson Lynch},
  TITLE         = {The Computational Complexity of {Portal} and Other {3D} Video Games},
  BOOKTITLE     = {Proceedings of the 9th International Conference on Fun with Algorithms (FUN 2018)},
  MONTH         = {June 13--15},
  YEAR          = 2018,
  ADDRESS       = {La Maddalena, Italy},
  PAGES         = {19:1--19:22},

  withstudent   = 1,
  doi           = {https://dx.doi.org/10.4230/LIPIcs.FUN.2018.19},
  dblp          = {https://dblp.org/rec/conf/fun/DemaineLL18},
  comments      = {The full version of this paper is available as
                   <A HREF="https://arXiv.org/abs/1611.10319">arXiv:1611.10319</A>, and from <A HREF="https://doi.org/10.4230/LIPIcs.FUN.2018.19">LIPIcs</A>.},
}

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 [1, 3, 7, 18].

Comments:

The full version of this paper is available as arXiv:1611.10319, and from LIPIcs.

Availability:

The paper is available in PDF (3331k).

See information on file formats.

[Google Scholar search]