论文标题
即使有$ O（1）$行或列，俄罗斯方块也是NP-HARD
Tetris is NP-hard even with $O(1)$ rows or columns
论文作者
论文摘要
我们证明，即使仅限于8列或4行，经典的掉落视频游戏Tetris（生存和董事会清算）仍然是NP的零件。我们的减少是从三粒分区的，类似于以前的无限制板尺寸的减少，但包装更好。在正面，我们证明了2列俄罗斯方块（和1行俄罗斯方块）是多项式的。我们还证明，即使板开始空，即使限制在3列或2列或2行或恒定尺寸的零件时，也将俄罗斯方块概括为较大的$ k $ -OMINO零件也是NP填充。最后，我们提出了动画的俄罗斯方块字体。
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 problems posed over 15 years ago [BDH+04]. Our reduction is from 3-Partition, similar to the previous reduction for unrestricted board sizes, but with a better packing of buckets. On the positive side, we prove that 2-column Tetris (and 1-row Tetris) is polynomial. We also prove that the generalization of Tetris to larger $k$-omino pieces is NP-complete even when the board starts empty, even when restricted to 3 columns or 2 rows or constant-size pieces. Finally, we present an animated Tetris font.
