算法与理论计算机2012arxiv.org
经典任天堂游戏是 NP 难问题（2012）
Classic Nintendo Games Are NP-Hard (2012)
进阶 · 约 90 分钟读完前置知识：计算复杂性理论基础、NP完全性、多项式时间归约
导读
这篇论文证明了《超级马里奥兄弟》《塞尔达传说》《俄罗斯方块》等经典任天堂游戏的广义版本在计算复杂性上是 NP-hard，部分游戏甚至达到 PSPACE-complete。做法是通过构造多项式时间归约，把已知的 NP-hard 问题（如布尔可满足性）编码成游戏关卡中的可通关性问题。
HN 关注点：HN 读者对童年经典游戏与理论计算机科学的交叉感到新奇，讨论焦点在于这些结论依赖对游戏规则的大幅推广，而非原版游戏本身。
后来怎么样
这篇论文开创了'任天堂游戏复杂性'系列研究，后续工作将多个经典游戏的结果推进到 PSPACE-complete 甚至更难，成为计算复杂性教学和科普中的经典案例。
HN 评论精选
这几条评论里：质疑 1 补充 2 亲历 1
质疑结论依赖对游戏规则的大幅推广，原版游戏并不 NP-hard
我一开始好奇这怎么可能成立，后来找到了这句话。他们的推广远远超出了这些游戏本来的样子（NES 马里奥在屏幕滚动时会把所有东西重置）。论文里说：例如在超级马里奥兄弟中，屏幕外的东西都会重置到初始状态，因此如果把关卡尺寸推广但保持屏幕尺寸不变，那么目标可达性可以在多项式时间内判定。
CJefferson查看英文原文
I wondered how this could possibly work, then found this sentence. Basically their generalisations have to go far beyond what these games are (the NES mario games had everything be forgotten when you scrolled along). > For example, recall that in Super Mario Bros. everything substantially off screen resets to its initial state. Thus, if we generalize the stage size in Super Mario Bros. but keep the screen size constant, then reachability of the goal can be decided in polynomial time:
补充猜测 NP-hard 程度可能与游戏经典耐玩度相关
有意思——不知道 NP-hard 能否作为游戏“挑战性是否恰到好处”的充分指标？这些游戏成为经典是有原因的，我觉得不完全是靠手感、打磨和营销。宫本茂的游戏总有一种特别的“味道”（个人观点），也许和这个有关？
headcanon查看英文原文
Interesting - I wonder if NP-hardness can be used as a sufficient indicator of how "enjoyably challenging" a game is. There's a reason these games are such classics, and I dont think its entirely because of their timing, polish, and marketing. Miyamoto's games always had that special "something" (opinion, I know), maybe this has something to do with it?
补充求科普 NP-hard 概念
有人能用几句话解释一下什么是 NP-Hard 吗？
fiatjaf查看英文原文
Can someone explain what is NP-Hard in a few sentences?
相关资源
从这篇论文所有 HN 讨论帖的全部评论里整理出来的链接。
历次讨论
- 2012Hacker News 讨论帖10 分 · 0 评
- 2012Hacker News 讨论帖16 分 · 0 评
- 2015Hacker News 讨论帖115 分 · 59 评
同领域还值得读
哲学家为何应关注计算复杂性
Why Philosophers Should Care About Computational Complexity (2011)
Scott Aaronson 的这篇长文论证计算复杂性理论（如 P vs NP、停机问题的复杂度视角）对哲学问题（如知识的本质、中文房间、水槽论证等）具有实质意义，而不仅是技术细…
算法与理论计算机2015 · 552 分 · 120 评进阶 · 约 90 分钟编辑精选通信的数学理论
A Mathematical Theory of Communication
是香农1948年的《通信的数学理论》，为通信建立数学框架：把信息量定义为不确定性或自由度（信息熵），并讨论信源编码、信道容量与可靠传输。
算法与理论计算机2020 · 495 分 · 91 评进阶 · 约 120 分钟编辑精选物理、拓扑、逻辑与计算：罗塞塔石碑
Physics, Topology, Logic and Computation: A Rosetta Stone (2009)
用范畴论充当“罗塞塔石碑”，试图在量子物理、拓扑、逻辑与计算四个领域之间建立统一的结构性类比：物理中的量子过程、拓扑中的配边、逻辑中的证明和计算中的程序，都可被视为某类范畴中的态…
算法与理论计算机2009 · 390 分 · 55 评 · 引用 13专业 · 约 180 分钟编辑精选一种快速、极小内存的一致性哈希算法
A Fast, Minimal Memory, Consistent Hash Algorithm
论文给出一种快速、省内存的一致哈希方案，目标是在桶数量变化时保持较小的键迁移成本，同时降低计算和内存开销。
算法与理论计算机2014 · 327 分 · 57 评 · 引用 4进阶 · 约 25 分钟编辑精选第五个 Busy Beaver 值的确定
Determination of the fifth Busy Beaver value
宣布确定了第五个 Busy Beaver 值 BB(5)：即 5 状态图灵机中停机前运行步数最多的机器（Champion）在 47,176,870 步后停机。
算法与理论计算机2025 · 288 分 · 116 评 · 引用 1专业 · 约 75 分钟编辑精选