The complexity of speedrunning video games
From MaRDI portal
Publication:3301017
DOI10.4230/LIPIcs.FUN.2018.27zbMath1489.68111OpenAlexW2811461449MaRDI QIDQ3301017
Publication date: 11 August 2020
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2018/8818/pdf/LIPIcs-FUN-2018-27.pdf/
Analysis of algorithms and problem complexity (68Q25) Game theory (91A99) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Parameterized complexity, tractability and kernelization (68Q27)
Cites Work
- Polynomial kernels for weighted problems
- Gaming is a hard job, but someone has to do it!
- Efficient algorithms for finding minimum spanning trees in undirected and directed graphs
- On fixed-parameter tractability and approximability of NP optimization problems
- Approximating minimum feedback sets and multicuts in directed graphs
- Lemmings is PSPACE-complete
- Classic Nintendo games are (computationally) hard
- Algorithmic construction of sets for k -restrictions
- Mario Kart Is Hard
- A fixed-parameter algorithm for the directed feedback vertex set problem
- Computational Complexity of Two-Dimensional Platform Games
- Minkowski's Convex Body Theorem and Integer Programming
- Super Mario Bros. Is Harder/Easier than We Thought
- Parameterized Algorithms
- Minesweeper is NP-complete.
This page was built for publication: The complexity of speedrunning video games
