The complexity of speedrunning video games

DOI10.4230/LIPICS.FUN.2018.27MaRDI QIDQ3301017zbMATH OpenOpenAlexFDO

Authors Manuel Lafond

Publication date 11 August 2020

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2018/8818/pdf/LIPIcs-FUN-2018-27.pdf/

zbMATH Keywords

approximation algorithmsparameterized complexityfeedback arc setknapsackvideo games

Mathematics Subject Classification ID

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)

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

Cites work

• A fixed-parameter algorithm for the directed feedback vertex set problem
• Algorithmic construction of sets for k -restrictions
• Approximating minimum feedback sets and multicuts in directed graphs
• Classic Nintendo games are (computationally) hard
• Computational complexity of two-dimensional platform games
• Efficient algorithms for finding minimum spanning trees in undirected and directed graphs
• Gaming is a hard job, but someone has to do it!
• Lemmings is PSPACE-complete
• Mario Kart is hard
• Minesweeper is NP-complete.
• Minkowski's Convex Body Theorem and Integer Programming
• On fixed-parameter tractability and approximability of NP optimization problems
• Parameterized algorithms
• Super Mario Bros. is harder/easier than we thought

Cited in

(1)

• Optimizing the video game multi-jump: player strategy, AI, and level design

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)