推荐dangrover · 2008-12
“kind of an interesting proof -- they reduce it to the problem of partitioning multisets of numbers into groups of equal sums”
觉得证明有趣:把问题归约为把数的多重集划分成和相等的组
证明离线俄罗斯方块的多种优化目标是 NP 完全且极难近似
在已知方块序列的离线版俄罗斯方块中,证明最大化消行数、最大化四行同消次数、最小化最大高度、最大化放置方块数这几个目标都是 NP 完全。进一步证明第一个和最后一个目标难以在 p^(1-ε) 因子内近似(p 为方块数),第三个目标难以在 (2-ε) 因子内近似。结论在多种规则变体下仍然成立。
评论者把它当作俄罗斯方块是 NP 完全的出处,提到证明用到数字划分的归约,也有人提醒这类结果针对的是广义版本。
“kind of an interesting proof -- they reduce it to the problem of partitioning multisets of numbers into groups of equal sums”
“For those that care, a few years ago some researchers proved Tetris is NP-complete for many problems.”
“Note that results like this [0] tend to be for generalizations.”
“It also has been shown that such a setup makes the game NP complete. Tetris is Hard, Even to Approximate”