2 papers
cs.CC2026
ASP-Completeness of Hamiltonicity in Grid Graphs, with Applications to Loop Puzzles
MIT Hardness Group, Josh Brunner, Lily Chung +4
We prove that Hamiltonicity in maximum-degree-3 grid graphs (directed or undirected) is ASP-complete, i.e., it has a parsimonious reduction from every NP search problem (including…
cs.CC2026
Tetris is Hard with Just One Piece Type
MIT Hardness Group, Josh Brunner, Erik D. Demaine +2
We analyze the computational complexity of Tetris clearing (determining whether the player can clear an initial board using a given sequence of pieces) and survival (determining wh…