TETRIS IS HARD, EVEN TO APPROXIMATE

DOI10.1142/S0218195904001354zbMath1093.90045OpenAlexW2146302034MaRDI QIDQ4818596

David Liben-Nowell, Hendrik Jan Hoogeboom, Susan Hohenberger, Ron Breukelaar, Erik D. Demaine, Walter A. Kosters

Publication date: 29 September 2004

Published in: International Journal of Computational Geometry & Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0218195904001354

zbMATH Keywords

computational complexityalgorithmic combinatorial game theoryTetris

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Game theory (91A99) Combinatorial optimization (90C27) Enumerative combinatorics (05A99)

Related Items (10)

Threes!, Fives, 1024!, and 2048 are hard ⋮ Online Square Packing ⋮ On the Complexity of Two Dots for Narrow Boards and Few Colors. ⋮ Bust-a-Move/Puzzle Bobble Is NP-complete ⋮ How fast can we play Tetris greedily with rectangular pieces? ⋮ Defying gravity and gadget numerosity: the complexity of the Hanano puzzle ⋮ On the complexity of jelly-no-puzzle ⋮ Online square packing with gravity ⋮ Combinatorial analysis of tetris-like games ⋮ An algorithmic analysis of the Honey-Bee game

Cites Work

• Unnamed Item
• Games against nature
• Complexity Results for Multiprocessor Scheduling under Resource Constraints
• Minesweeper is NP-complete.

This page was built for publication: TETRIS IS HARD, EVEN TO APPROXIMATE