Tetris is NP-hard even with O(1) rows or columns [pdf]

26 isaacfrond 4 9/1/2025, 12:49:57 PM martindemaine.org ↗

Comments (4)

relwin · 9m ago
Why is the paper's copyright footer "1992 Information Processing Society of Japan" when this work is actually from around 2019?
ansgri · 5m ago
Probably used an outdated LaTeX template.
dooglius · 11m ago
Needs (1992)
pretzellogician · 1h ago
Interesting! Not really that surprising, since another dimension (rows/columns/piece size) is O(n). But pretty cool.