足，还有12年多的时间。”格雷厄姆还抱有更大的希望：“在以后3年内得到证明也不会让我吃惊。”
尽管人们普遍乐观，但在综合性理论方面（数学的一个分支学科，它表述了问题的难度）的研究人员，以他们的直觉已经知道他们会失败的。1985年冬天，美国麻省理工学院的数学研究生戴维·巴林顿曾证明，计算机能够运算的某些原始表示法会比该领域中任何人所能设想的更有功效。这种原始表示法不包含“与”门、“或”门和“非”门，但却包含一个分支门，它也有两根输出引线。当分支门受到触发时，如果输入信号具有一定的指定值，则分支门就会沿两根引线之一送出一个信号；对于所有其他输入信号，分支门沿另一根引线送出一个信号。换句话说，分支门能够处理计算机程序中的语句，诸如“如果x=5，转向步骤4；对于所有其他x，转向步骤7”。
巴林顿又证明了，全部由门层次不超过5层的分支门构成的电路，可以解所谓的多数问题：在一串的0和1中，1是不是多数？综合性理论学家普遍地（并且错误地）认为分支门限制于任何固定高度，不可能求解多数问题，更不用说严苛的五层限制了。
巴林顿说道：“我的证明很简单，但它令人惊奇，因为他们总是认为我所试图证明的都是假的。”巴林顿的结果也许没有多少实际用途——他又说：“除了它可以让我在一所好大学获得一个教师职位之外。”而且它还可以说服数学家们不要在复杂的综合性理论领域中如此自信。
________
① 如果你一定要知道的话，NP表示非决定性的多项式，而complete一词则意味着这些问题是该类问题中最难的。