scientific article; zbMATH DE number 7829453

arXiv2203.17167MaRDI QIDQ6126484

Unnamed Author, Erik D. Demaine, Jayson Lynch, Michael J. Coulombe, Jeffrey Bosboom, Dylan Hendrickson, Unnamed Author

Publication date: 9 April 2024

Full work available at URL: https://arxiv.org/abs/2203.17167

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

hardnessPSPACENPvideo games

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parameterized complexity, tractability and kernelization (68Q27)

Cites Work

• Unnamed Item
• Unnamed Item
• Gaming is a hard job, but someone has to do it!
• Classic Nintendo games are (computationally) hard
• Relationships between nondeterministic and deterministic tape complexities
• PSPACE-Completeness of Bloxorz and of Games with 2-Buttons
• The Computational Complexity of Portal and Other 3D Video Games
• On two geometric problems related to the travelling salesman problem
• Computational Complexity of Two-Dimensional Platform Games
• Hamilton Paths in Grid Graphs

This page was built for publication: