停机问题：一个很糟糕的 NP-Harder 例子
The Halting Problem is a terrible example of NP-Harder
这是一个可以理解的权宜之计，但仍然是权宜之计。
这次内容较短，因为这周事情很多。
在计算复杂度中，NP 是所有判定问题（是/否）的集合，其中对于“是”的潜在证明（或“见证”）可以在多项式时间内被_验证_。例如，“这个数字集合是否存在加起来等于零的子集”属于 NP。如果答案是“是”，你可以通过提供一个数字集合来证明它。然后，我们将通过 1) 检查所有数字是否都在集合中（约线性时间）和 2) 将所有数字相加（也是线性时间）来验证该见证。
NP-complete 是“最难” NP 问题的集合。Subset sum 是 NP-complete。NP-hard 是_至少与_ NP-complete 一样难_的所有问题的集合。值得注意的是，NP-hard 不是 NP 的子集，因为它包含_比 NP-complete _更难_的问题。一个很自然的问题是“比如什么？” 而 “NP-harder” 的典型例子是停机问题 (HALT)：程序 P 在输入 C 上是否会停机？ 正如论点所说，它是不可判定的，所以显然不在 NP 中。
我认为这是一个糟糕的例子，原因有两个：
- NP 所要求的只是对“是”的见证可以在多项式时间内验证。它对“否”的情况没有任何要求！ 即使 HP 是不可判定的，也_有_一种可判定的方法来验证“是”：让见证是“它在 N 步内停止”，然后运行程序那么多步，看看它是否在那之前停止。 要证明 HALT 不在 NP 中，你必须表明这个验证过程的增长速度快于多项式。 它的确如此（因为 busy beaver 是不可计算的），但这使得这个例子变得毫无必要地令人困惑。Footnote 11
- “什么比狗大？ 月亮”
真正困扰我的是 (2)，而不是 (1)，因为它太不优雅了。它暗示 NP-complete 是“可解”问题的上限，之后你就完全进入了不可判定性。 我宁愿展示一些比 NP 更难但又不是_那么_难的直观问题。
但在寻找“稍微难一点”的问题时，我遇到了一个问题。看起来下一个最难的类是 EXPTIME， 除非我们不能_确定_ NP != EXPTIME。我们_确定_ NP != NEXPTIME，但 NEXPTIME 没有任何直观的、容易解释的问题。 大多数“肯定比 NP 难”的问题都需要在理论计算机科学或数学方面有相当的背景才能理解。
但是，有一个问题我觉得很容易解释。将一个token放在无限向上和向右延伸的网格的左下角，称该点为 (0, 0)。 你会得到一个token的有效位移移动的列表，比如 (+1, +0)，(-20, +13)，(-5, -6) 等，以及一个目标点，比如 (700, 1)。你可以按任何顺序进行任何移动序列，只要任何移动都不会使token离开网格。 是否有任何移动序列能将你带到目标？
我认为这是 PSPACE-complete，但这仍然没有被证明比 NP-complete 更难（尽管人们普遍认为如此）。但是，如果你增加网格的维度呢？超过一定的维度，问题会跳到 EXPSPACE-complete，然后是 TOWER-complete（以 tetrationally 的速度增长），然后它会继续增长。有人可能会认识到这看起来很像 Ackermann function，事实上，这个问题在可用维度数量上是 ACKERMANN-complete 的。
一位朋友写了一篇关于整个乱象的 Quanta 文章，你应该读一下。
这个问题比 NP 大得离谱（“芝加哥”而不是“月亮”），但至少它显然是可判定的，容易解释，而且肯定_不在_ NP 中。
- 如果你被教导了 NP 的另一种（也是最初的！）定义，“可以通过非确定性 Turing machine 在多项式时间内解决的问题类”，那就不会那么令人困惑了。 那么 HALT 不可能在 NP 中，否则运行时将受到指数函数的限制。 ↩
如果你在网上阅读这篇文章，你可以在这里订阅。每周更新一次。我的主网站是这里。
_我的新书，_Logic for Programmers ，现在正在早期访问！ 在这里获取。