Tetris is Hard, Even to Approximate
From MaRDI portal
Publication:3082942
DOI10.1007/3-540-45071-8_36zbMath1276.68081MaRDI QIDQ3082942
David Liben-Nowell, Susan Hohenberger, Erik D. Demaine
Publication date: 18 March 2011
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/3-540-45071-8_36
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Related Items
LaserTank is NP-Complete, Hanabi is NP-hard, even for cheaters who look at their cards, The complexity of flood filling games, Tetravex is NP-complete, On a generalization of ``eight blocks to madness puzzle, Tetris and decidability, Wooden geometric puzzles: Design and hardness proofs, The computational complexity of Angry Birds, Twenty years of progress of \(\mathrm{JCDCG}^3\), Graph kernels and Gaussian processes for relational reinforcement learning, The complexity of comparing optimal solutions, The Computational Complexity of Portal and Other 3D Video Games