6 citations · 6 across the 3 of their papers we have counts for
3 papers
Tetris is NP-hard even with rows or columns
Sualeh Asif, Michael Coulombe, Erik D. Demaine +4
We prove that the classic falling-block video game Tetris (both survival and board clearing) remains NP-complete even when restricted to 8 columns, or to 4 rows, settling open prob…
Hamiltonicity in Semi-Regular Tessellation Dual Graphs
Divya Gopinath, Rohan Kodialam, Kevin Lu +2
This paper shows NP-completeness for finding Hamiltonian cycles in induced subgraphs of the dual graphs of semi-regular tessilations. It also shows NP-hardness for a new, wide clas…
The Computational Complexity of Portal and Other 3D Video Games
Erik D. Demaine, Joshua Lockhart, Jayson Lynch
We classify the computational complexity of the popular video games Portal and Portal 2. We isolate individual mechanics of the game and prove NP-hardness, PSPACE-completeness, or…