数学家们曾开玩笑说，若要长生不死有一个办法，就是找到这样一个问题，它极其重要，重要到你不解决它就不能够死，然后你就把它束之高阁，不去解决它。在计算复杂性理论的领域中，多项式分层结构问题好像正合那些想永远不死的人的意。它很困难一是那样地难，以至于就像美国电话电报公司贝尔实验室的罗纳尔德 · 格雷汉（Ronald Graham）形容的一样，“多少数学家为它折断了笔。”它很重要——几乎成为理论计算机科学上最重要的课题。甚至在前不久，它仍被看作是在可预见的将来也是难以解决的。

但是现在斯坦福大学的安得鲁 · 姚（Andrew Yao）提出了一种非常繁复的证明，虽然它不能直接用来解决问题，但是至少能给数学家们提供进门的台阶。格雷汉说，这是解决这个问题的“最令人鼓舞的进展之一”。虽然姚还在写他那短短的约二十五页纸的成果，然而数学家们却已经开始从世界各地打电话、电报向他祝贺。

这个问题的实质，就是要确定在计算机上解题的难度，即“硬”度。研究者们已经根据解题所需要的时间长短，把问题进行了分类，由此产生了所谓“多项式分层结构”的问题，看来解这类问题的困难很大。然而，这个分层结构的确存在吗？它是否真正反映了问题的本质，或者它仅仅是反映了我们的解题能力不够呢？是不是有可能连处在最高层次的最硬的问题实际上也是容易解决的呢？大部分计算机科学家们都相信分层结构是存在的，但是要证明这一点却是困难的。这个问题也正是姚的成果所涉及的。

在分层结构的底层是那些比较容易解决的问题。解题所需要的步数，只是问题规模的多项式函数。例如，一个问题有n个变量，那么用n²步就可解决了。在这种情况下，计算量随问题规模的增大增加得很慢。如果n从10扩大到20，那么计算步数，n²只增加了四倍。因为在计算机科学中，解题所需要的步数与所需时间量成正比，所以研究者给它们起了一个名称——多项式时间或简称为P，用来描述这类问题。

在多项式时间问题之后，按分层结构排序，问题的硬度逐步增加，它们都被归为指数级时间问题，即求得一个通解所需的计算次数是一个问题规模的指数函数。例如，一个问题有n个变量大概要2ⁿ步，这就是以n为指数的函数。在这种情况下，如果n从10增加到20，解题所需步数就增加了1000倍。解指数级时间问题需要的步数是相当长的，以至在大多数情况下就根本无法想象在计算机上能够得到结果，研究者不得不用特殊条件下的或者近似的解来代替它。

分层结构的第二屋是NP类问题的集合，NP就是未确定型多项式时间。这些问题没有已知的多项式时间算法，但是它给出了一个可能的解，可以用多项式时间来检验它。

最常见的NP问题之一是著名的流动售货员问题。比如一个售货员要订出这样一个计划，他的时间只够走5000英里，但是要走遍六十个城市，每个城市只去一次。能否找到这样一条路线呢？麻省理工学院的米切尔 · 西普塞（Michael Sipser）说，“要验证一条已给出的路线很容易，但是要把它找出来却肯定是个硬问题”。非但硬，这个问题还是十分重要的，它令许多公司感到头痛，其中有需要计划路线的航空公司和需要在装配印刷电路板时确定最佳工序的电话公司。

有一种解决流动售货员问题的笨办法，就是先找出所有可能的路径，然后从中寻得一条最短的。虽然这种办法十分繁琐远不是巧妙的，但还不曾有什么人已有另一种显然是更好的方法来解所有可能的流动售货员问题并且总能得出最短路径。如果有六十个城市的话，这个算法就肯定超过10¹⁹步，所需步数随城市数目的增加以天文数字的数簠级增大。为了寻找实际流动售货员问题的答案，计算机科学家已经设计了几种方法，它们较以前的凭一味硬干要快些，但不是保证总能找出最佳路线。代之以最佳路线的是一条不太差的路线。

另一个NP问题是哈密尔顿路径问题。给出一个图，它是一个点的集合，是通过线相关联，要求确定，是否能找出这样一条路线，使得每一个点都在这条线中、并且这条线经过每一个点只有一次？这与流动售货员问题很像，不过不足要求出最短路径，而是要求出是否能画出这么一条路径。

像NP问题一样硬的问题，还仅仅处于研究的起点。在分层结构的分类中，计算机科学家把它们区分出来；因为它们都有同样的形式，“存在着……”，问题的回答总是“Yes”或者“No”。比方流动售货员问题，它就可表示为“存在一条5000英里的路径”。哈密尔顿路径问题可表为“存在一条哈密尔顿路径。”

再往上一层是另一些问题的集合，它们可表为“对于所有的……存在……”，西普塞举例说“一个图上的线可以代表从东北来的道路。有一半道路可能由于下雪而不能通行。那么是否保证存在一条哈密尔顿路径？”或者“用所有可能的办法把图中一半的边去掉，是否存在一条哈密尔顿路径？”

向上第四层是形如“对所有的……存在……对所有的……存在……”的问题。例如，用所有可能的办法把图中二分之一的边去掉，其中存在二分之一的边可选出重新放回，使得可用所有可能的办法把其中四分之一的边再去掉，最后在图中剩下部分存在一条哈密尔顿路径。第五层是形如“对所有的……存在……对所有的……存在……对所有的……存在……”的问题，分层结构按此类推，在它的顶端就是数学家所谓的“多项式空间”的问题。

伯克利加利福尼亚大学的里查德 · 卡普（Richard Karp）说，你可以把多项式分层结构看作是轮流动作的比赛，多项式时间问题好比是必胜赛，只有一个参赛者，结果当然是固定的。分层结构的第三层次好比是一场你和你的对手每人只可动作一次的比赛。比赛虽短但却很难说出谁将取胜。第四层次就好像在比赛中动作的总次数规定为3。谁会取胜仍旧不得而知。卡普说，“多项式空间也可被看作一场角逐，不过它没有固定的动作次数。就像下棋或者拳击比赛，这样的问题是要在第一个竞赛者走了第一步后来确定谁会赢”。

让计算机科学家犯难的事是确定多项式分层结构是不是真实的，或者说每一层中的问题是否都有相同的性质，也就是说，在多项式时间层中所有的问题都真正是快速可解的。如果分层结构中问题层之间至少存在某些本质的区别，那么是不是就说明分层结构的整体都是层次分明的，或者说某些分层会不会有重叠呢？假设确有一个分层结构，那么它的边界划在哪里？还有，多项式空间是不是的确与分层结构中的其他层次不同呢？

这些问题在现实中是极为重要的，因为它们天天要被提出来，它们是否有直接的解，是否真像表面上看起来的那样困难，虽然答案至今还未找到。如果这个多项式分层结构是真实的，我们能期望得到的最好结果是，对这些非常困难的问题有一个近似的解。

有一段时期，在许多研究者看来，借助于数理逻辑的方法可找出多项式分层结构问题。他们主张把问题完全抽象出来，在另一个世界里只需考察一下问题的逻辑结构就行了。根据逻辑学家们的这个推理，设想有这么一个“神使”位无所不知的圣人，他能给你的特定问题一个解答。比方说，这位圣人也许有一份可找到一个哈密尔顿路径的全部可能图的清单。那么如果你想要知道你的图是否有一条哈密尔顿路径，只要向这位圣者打听一下你的图是否在它的清单中。

不过这位圣人的行为有些古怪。有两组研究者，一组是斯坦福大学的约翰 · 吉尔（John Gill）和伯克利加利福尼亚大学的罗伯特 · 索罗伐（Robert Solovay），另一组是佛罗里达州立大学的西奥多 · 贝克（Theodore Baker）和依阿华州立大学的阿兰 · 塞尔受（Alan Selman），他们独立地证明了，存在某些“圣人”，它们把称为NP的问题，即分层结构中的第二层问题都归入第一层P。另外也存在某些圣人，它们把P和NP完全区分开来。正如科奈尔大学的朱里斯 · 哈特曼尼斯（Juris Hartmanis）所说，“结果让人目瞪口呆”。

计算机科学家依然认为，如果多项式分层结构确实是一个分层结构的话，那么就应该有一个圣人，它能够把问题级别的整个排列逐一分解开来。但他们还是陷入了困境。他们能够证明，存在某些圣人能够把第四层的问题从P和NP中区别出来，但没有一个圣人能作进一步的区分。

几年前，西普塞同卡内基 - 梅隆大学的麦里克 · 弗斯特（Merrick Furst）和简姆斯 · 塞克斯（James Saxe）在一起工作时，发现了另一种找出多项式问题的途径。西普塞说，他们发现“这些问题基本上可转为 · 对布尔线路图（Boolean Circuits）的探讨，”对计算机硬件设计者来说，这些线路图是他们所熟悉的计算机的“与”和“或”的门网络。计算机的信息以二进制码加以贮存，计算机把这些二进制码用“与”和“或”的功能联结起来。西普塞说，“只要你有了这些线路图，你就能计算任何东西。想象一下，现在你正在建立一个能告诉你如何解P级和NP级问题的网络。如果你能证明NP所需网络一定比P所需的网络要大，那么你就证明了P不等于NP”。

然而没人知道如何证明NP以及在分层结构中较高层次问题的布尔线路图一定大。西普塞和他的同事们正在考察网络的限制性因素，西普塞问道，假设网络能根据你的需要随意增大而没有深度限制的话，你能不能证明在多项式分层结构的层次间确有差别呢？三个探索者考察了奇偶功能，仅仅计算在一长串码中是否存在一个偶数或奇数，他们发现，如果限制了线路网的深度，它的宽度就会增加使之比任何多项式都大。

这项发现虽然令人兴奋却也不能充分地表明，在限制性条件下多项式分层结构是层次分明的。最终是姚取得了成果，现在他已证明了，有奇偶功能的布尔线路网的宽度比西普斯、弗斯特、塞克斯和艾叶太所发现的增加得更快。它的增长呈指数级，无疑比多项式增长要快。作为这项成果的结果和扩展，他证明存在一位圣人，对圣人来说多项式分层结构是层次分明的。

姚说这是“一个复杂的证明”。西普塞把它描绘成是“繁琐而深奥的但不是一个巧妙的把戏”。然而，姚、西普塞和其他人都认为，这个证明的真正涵义远远超出了发现多项式分层结构在这位圣人的陌生世界中是可区分的这一点本身。事实上姚认为，虽然数学家们找出的圣人意见分歧，他们的工作却向证明没有圣人，多项式分层结构也照样存在迈出了“建设性的一步”。有些人对此满怀热情，而另一些人却说这项成果与我们这个实现世界没有明显的联系。

即使是对圣人抱怀疑态度的人也不得不承认，姚的证明的真正重要性在于表明了，布尔线路网这种组合计算法可能被用来考察多项式分层结构问题。

格雷汉解释说，“对许多人来说，安迪的成果提供了真正的证据，证明我们能通过考察复杂的组合理论了解到许多东西。然而人们至今还没有真正对线路网加以研究。我希望他的成果会促使人们推进这种方法。现在已有很大的希望让线路网带来一些新的成果。”

如果线路网真能解决多项式分层结构问题，并且也不需要一个圣人的话，那么研究者将应扩大他们的成果使线路网不受限制地能达到任何需要的深度。这行得通吗？西普塞就是一个持肯定意见的人。“我对于怎样使线路网不受约束有许多想法”，他说，“让我只说一句，我有足够的信心要花大量时间为之努力。”

最后，这个高度抽象的研究还有一项小小的实际运用。某种称为可编程序逻辑阵列的线路网可以方便地用在集成电路块上，西普塞指出，“它有内在的深度限制”。计算机工程师曾经认为，有某些运算是不能在线路网上实现的，一个是奇偶功能，另一个是乘法功能，西普塞说：“每一个人都知道，你无法在一个可编程序逻辑阵列上实现奇偶或乘法功能，但是没有人能证明这一点，而现在我们却知道了为什么不可能。”

[Science，1985年4月]