4. 数学

1928年，数学泰斗大卫·希尔伯特提出了他伟大的判定性问题（Entscheidungsproblem），即能否找到一个能正确判定任意数学命题真伪的算法。1931年库尔特·哥德尔证明，必然存在某些命题，它们根本不能被任何公理系统的集合证实或证伪。受哥德尔工作的影响，几年后，阿隆索·丘奇和阿兰·图灵分别独立证明了不存在满足判定性问题要求的算法。

但如果我们做出限定，即命题所需证明的长度必须短到可以在一本很薄的书上写出来，这样有可能找到判定算法吗？我们可以通过计算来求解这个问题，只要穷举对于给定数学命题的所有可能的短小证明就可以了。这是一个NP问题，因为如果给定一个证明，我们容易判断它是否有效，但是找到一个有效证明实际上很困难。这也是为什么数学家能通过巧妙地证明某些数学命题而博得声誉的原因。

有时候找出让某些形式简单的逻辑表达式为真的方法都很困难。对这个问题的研究直接促成了一个能将大部分NP问题都联系起来的理论的形成。我们在下一章讲讲这个故事。