墨菲法则（Murphy slaw）*可能正在等待机会使数学家们大吃一惊——
我为墨菲法则而烦恼，不是因为它使得生计艰难——我已习惯于此——而是因为它没有使生计难到应有的程度。按照墨菲法则，凡有可能出差错的事终将出差错，那么为什么它仿佛没有发生呢？
数学具有另一个令人徨惑的因素：哥德尔定理。七十年前，哥德尔演示出必定存在某些数学的陈述，它既不能被证明也不能被否定。他指出数学必定有逻辑上的漏洞。确实，哥德尔和墨菲联起手来会为数学添乱。哥德尔说数学可能出差错，墨菲说因此它必定会出差错。数学会由于许多无法证明的概念而变得一团糟。
在哥德尔出现之前，数学看来不大可能是墨菲活动的场所。希尔伯特，这位二十世纪初期的数学家，相信整个学科可能建立在一些简单的逻辑原理上，并且他领导了一个庞大的计划去建立这个精细的逻辑基础，到那时已成为不成问题的定理——例如1+2=2——使得人们瞠目结舌。我们是如何知道这些的？例如“1”和“十”指的是什么？
希尔伯特想要从最基本的可能的水平开始，用到几条称为公理的明白无疑的陈述——诸如X+0=X（加上零不会使一个数增大）。他旨在演示能推导出数学的全部而不会引出矛盾，仅将简单的逻辑应用于这些公理就行了。
希尔伯特相信，这种戏法是把数学看作为以任意符号为道具的一种游戏（逻辑规定如何运用这些符号）。如果你能证明这些规则永远不会自相矛盾，就万事大吉了。
但是正当希尔伯特和他的学生们认为看到通道尽头的亮光的时候，哥德尔闯进来了，那时他已结束了希尔伯特的纲领。他不仅熄灭了亮光，还已证明了从一开始就不存在这一条通道。
图为德国数学家希尔伯特
哥德尔使希尔伯特的一些概念自相矛盾。他发明了一种逻辑的构架，在其中一条算术的陈述能认定——以一种精巧的编码形式——“这条陈述不能被证明是真的”。如果此陈述是假的，则它能被证明是真的，这样你看到了一个矛盾。所以它必定是真的。但是这意味着你不能证明它。
还有没有什么与此有关的方式？好，有许多方式为算术构造出一种逻辑的构架。你有一些自由去选择你的公理并仍然得到一个包含1+1=2成立的算术的型式的结果。例如，你能从定义加法开始，并运用这去推导乘法。或者你能定义乘法并用以做加法。
但是哥德尔指出，不管你怎样建立你的系统，它必定仍然包含一些不可判定的陈述。并在给定一条这类陈述之后，将存在一种算术的形式化使这条陈述在其中可能是真的，也存在另一种算术的形式化使它在其中可能是假的。并还有其他的算术的形式化，使它在其中仍然是不可判定的。
有几个问题已经被证明是不可判定的。其中之一是“停机问题”。英国数学家图灵（Alan Turing）引进一种图灵机——关于数字计算机的一种数学的形式化——的概念。当你在图灵机中运算一种程序时，要么它停止并打出一个答案，要么它永远运算下去。例如以下的一种程序：
1.到第二行
2.停
显然停机了，然而
1.到第一行
2.停
不会停机，因为它永远不会到达第二行。问题是去求得一种系统的方法来事先决定一种给定的程序是否会停机。
图灵证明了停机问题是不可判定的。为了演示这一点，他作了许多哥德尔式的游戏。假定停机问题是可判定的，图灵指出你能构造出一种程序，即仅当它不停止时才停止。这是胡闹，所以此假定是假的。
俄罗斯数学家马提耶什维克（Yuri Matijasevic）发现了另一种不可判定的命题：是否存在一种系统的方法来决定一个代数方程有无至少一个整数解？实质上，他的证明表明，此代数方程能表现得像一种图灵机那样。
但是至今这些研究中没有一个对于主流数学有很大冲击，哥德尔的概念改变了数学家们关于他们的学科的深层基础的思想方法。但是它们没有对于日常研究产生很大影响。这看起来很奇怪，尤其是因为主流数学给墨菲提供了大量机会——总存在一些未解决的大问题要每个数学家殚精竭虑去解决它们。
例如，1950年左右，最热门的这类大问题中的三个是费尔马大定理、四色问题和开普勒猜想。第一个问题说两个完全立方体不可能拼成一个完全立方体，对于五次和所有的高次立方体也是如此。第二个问题说每个地图能用四种颜色着色，其中相邻的区域总用不同的颜色。第三个问题说要将球体堆积得最紧密的方法就是水果摊上堆积橘子呈重叠的六边形图案的那种方法。
三重打击
所以我们有了三个未解决的大问题。哥德尔告诉我们数学问题不是必有一个完全确定的解，留给墨菲去闯的机会看来是不可抵抗的。在这些重要的问题中哪怕有一个结果是不可判定的吗？然而墨菲错了，四色问题于1976年被K · 阿佩尔（Kenneth Appel）和H · 哈肯（Hermann Haken）证明出来，费尔马大定理于1994年被A · 怀尔斯（Andrew wiles）攻克，并且开普勒猜想于2000年被T.黑尔斯（Thomas Hales）证明出来。所有三个猜想结果都是真的。
什么原因使得墨菲的成功的步伐落得一个停止呢？如果看一下他早期的成功，一种模式出现了，它们都是超问题（meta-problem）——关于问题的问题。希尔伯特想要使数学成为一个用来决定任何给定的陈述是否真的一般方法，而哥德尔证明了它不可能是这样的。图灵也否定了用于去回答：“这件事会停止吗？”这个问题的一般方法存在的可能性。似乎是主流数学——超数学的对立面——的重要部分是墨菲的禁区，而墨菲的要害全在于不应有禁区。
这使得许多数学家不安。所有的不可判定的问题在何处呢？为什么仅有几个潜伏在超数学的边缘？我猜测其解答是：当它进入数学中时，墨菲既是精巧又是诡诈的。有一个真正未解决的大问题可能是墨菲去活动的合适的领域。确实它有点像一个超问题，但是在解答它时会告知我们关于许多有趣的、具体的问题的某些重要事情——它是在主流数学中真正有趣的。
在我想象中的这个问题称为“P=NP？”。并且如果能解决它你能得到100万美元，此奖金是由克莱数学学院提供的七个奖项之一，每项值整整100万。但规定是严格的：你的解答必须发表在主要数学杂志上并被数学界接受持续几年之久——所以你不要试着投寄给我。
“P=NP？”仅是一个编成代码的问题，是关于计算机算法的有效性的。其基础的问题是：当问题的尺度变大时计算时间如何快速地增加？某些问题能用一台计算机快速地解决，甚至对大量的输入数据也行。
不难理解，我意指所需要的计算步骤次数至多正比于问题尺度的一个固定次数乘方。我们称这一类算术以多项式时间（polynomial time）运转，或是属于P类。
一个例子是把一长列的字按字母次序编排，其最简单的做法所用的时间正比于字数的平方。所以编排十个字所用的时间是编排5个字的时间的四倍。如果你想编排电话簿上的名称你需要有一台相当快的计算机，但是它做得到。
一个困难得多的任务是旅行售货员问题。一位售货员必得走遍若干城镇，他必须以什么次序走遍所有城镇使得总路程为最小？一种方法是去考虑所有可能的路线并仅仅挑出最短的一条。麻烦的是，路线数目的增加快于城镇数目的任何次乘方。你也许能就10个或20个城镇立即解决这个问题，对于100个城镇呢？让它去吧，还没有人知道是否存在一个较快的P类方法。
我们对于这个问题所知的是，你能相当快核实任何给定路线是否最短的。这有点像一个交错搭接难题：求一个解要费大量工作，但是你一目了然就能知道这个难题是否已经解决。对于旅行售货员问题如何做到这一点不是很明显，但是你能事实上以多项式时间去核对出一条已知路线是否最短的。这将旅行售货员问题放入NP类，它表示不确定的多项式时间（noncleterministic polynomial time）。
问题P=NP？就是问每一个NP问题实际上是否P类的。换句话说，如果一个问题的解答能用多项式时间得到核实，它总能以多项式时间求出吗？
初看起来，对于P=NP？的解将肯定是无解。求得某个问题的一个解答应当比核实它（当有人已经求得它时）困难些，至今还没有人能证明或否定它。这就是还有100万美元在等待得主的原因。
P=NP？这个问题显示了墨菲对数学的破坏，幸亏一种称为“NP—完备性”的奇异现象。它表明了许多外表上不同的NP问题实际上是编成不同方式的同一个问题。所以能解决出这些问题中的一个的多项式时间算法也适用于其他问题。事实上，这些NP的某些个能重新编织成每个NP问题。如果求得一种多项式时间算法解决了旅行售货员问题，你就已经求得了一种能适用于所有NP问题的多项式时间算法。所有这类难题将一下子变得大大容易了——不仅是难解的数学问题，而且是实际工作诸如数据压缩并有效地裁剪布料或金属片等。
不幸，数学家们发现事实上每一个有趣的NP问题是NP完备的。这意味着如果你想要解决任何一个NP—完备的问题，你不能用把它转化为一个简单的问题这个拿手的技巧来解决它，因为其难度都是不相上下的。
所有这些事实诱使我不顾一切后果并猜测P=NP？是不可判定的。但记住这类问题是如何滑溜——它们能在数学的不同型式中成为可判定的，这依赖于你所选择的公理的集合。所以如果P=NP？是不可判定的，然后你能证明它是不可判定的，则必定存在一种数学的相容的形式化，在其中有P=NP。在这样一种形式化中，所有的如旅行售货员这类使人神魂颠倒的问题将有一个快速的容易的答案，这将是数学家们的一个乐园，并肯定墨菲将不允许这类事情存在。
所以，如果P=NP？确是不可判定的就不知道怎样了。但是你不能证明它——关于它是否不可判定的这个问题本身也是不可判定的。到那个水平上，数学家们仍能找到他们的P=NP乐园。首先变更公理使得P=NP有可能是不可判定的。然后再次变更公理，使得它真是不可判定的。
但是如果墨菲的计划是不可判定性的、一个没完没了的回归，事情看来惨了，则不存在一种层次在其中不可判定性会得到证明，我们将无限地需要新的公理去达到P=NP，并且乐园将真的是遥不可及。
凡事可能变错，就一定会变错。墨菲变了。
[New Scientist，2001年9月15日]
—————————
译者注:墨菲法则( Murphy's law),一种认为凡有可能出差错的事终将出差错的俏皮论断。