Tetris Is Np-Hard Even with O(1) Rows or Columns (2020) [pdf]
Posted4 months agoActive4 months ago
martindemaine.orgSciencestory
calmpositive
Debate
20/100
Computational ComplexityTetrisNp-Hardness
Key topics
Computational Complexity
Tetris
Np-Hardness
A 2020 paper proves that Tetris is NP-hard even with a constant number of rows or columns, sparking discussion about the game's complexity and related topics.
Snapshot generated from the HN discussion
Discussion Activity
Active discussionFirst comment
2h
Peak period
11
0-6h
Avg / period
3.8
Comment distribution19 data points
Loading chart...
Based on 19 loaded comments
Key moments
- 01Story posted
Sep 1, 2025 at 8:49 AM EDT
4 months ago
Step 01 - 02First comment
Sep 1, 2025 at 11:16 AM EDT
2h after posting
Step 02 - 03Peak activity
11 comments in 0-6h
Hottest window of the conversation
Step 03 - 04Latest activity
Sep 3, 2025 at 5:15 PM EDT
4 months ago
Step 04
Generating AI Summary...
Analyzing up to 500 comments to identify key contributors and discussion patterns
ID: 45092324Type: storyLast synced: 11/20/2025, 2:49:46 PM
Want the full context?
Jump to the original sources
Read the primary article or dive into the live Hacker News thread when you're ready.
These are things filled in by the journal in the proofing stage (after peer review).
https://simon.lc/the-history-of-tetris-randomizers
> Nand to Tetris courses are taught at 400+ universities, high schools, and bootcamps. The students who take them range from high schoolers to Ph.D. students to senior engineers. Here is an extended syllabus of a typical academic-version course.
There's now a schema.org/Syllabus Class .
> Similar: "Show HN: Tetris, but the blocks are ARM instructions that execute in the browser" https://news.ycombinator.com/item?id=37086102
What is the computational complexity of Tetris with ARM instructions?
In ASM;
Rosetta Code > Tetris: https://rosettacode.org/wiki/Tetris :
> tetromino.py - Python implementation of Tetris included with Raspbian
If it is Turing complete it is undecideable. If the user only builds programs that halt, is Teris with ARM instructions of the complexity class NEXPTIME-complete (which is harder than NP-Complete)?
NEXPTIME: https://en.wikipedia.org/wiki/NEXPTIME
Complexity Zoo:N: https://complexityzoo.net/Complexity_Zoo:N