The complexity of speedrunning video games
From MaRDI portal
Publication:3301017
DOI10.4230/LIPICS.FUN.2018.27zbMATH Open1489.68111OpenAlexW2811461449MaRDI QIDQ3301017FDOQ3301017
Publication date: 11 August 2020
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2018/8818/pdf/LIPIcs-FUN-2018-27.pdf/
Recommendations
- scientific article; zbMATH DE number 16390
- The computational complexity of Portal and other 3D video games
- On timeline-based games and their complexity
- Computational complexity of two-dimensional platform games
- The computational complexity of Angry Birds
- Complexity of question/answer games
- On the complexity of speed scaling
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Game theory (91A99) Parameterized complexity, tractability and kernelization (68Q27)
Cites Work
- A fixed-parameter algorithm for the directed feedback vertex set problem
- Minkowski's Convex Body Theorem and Integer Programming
- Parameterized Algorithms
- Algorithmic construction of sets for k -restrictions
- Efficient algorithms for finding minimum spanning trees in undirected and directed graphs
- Approximating minimum feedback sets and multicuts in directed graphs
- Polynomial kernels for weighted problems
- Minesweeper is NP-complete.
- Computational Complexity of Two-Dimensional Platform Games
- Gaming is a hard job, but someone has to do it!
- On fixed-parameter tractability and approximability of NP optimization problems
- Classic Nintendo games are (computationally) hard
- Mario Kart Is Hard
- Lemmings is PSPACE-complete
- Super Mario Bros. Is Harder/Easier than We Thought
This page was built for publication: The complexity of speedrunning video games
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3301017)
