仅仅是惟一的计算问题，许多数学家都不理解其快速算法。还有一整套叫做NP-完全的问题，对于这类问题，人们仅知道其计算所需时间以指数方式激增。①在NP-完全的问题中，另有一个众所周知的例子称为人群问题：已知有一大群人，比方说，共100人，他们之间是否有许多人，比方说，有50个人，全都彼此认识吗？

    “你可以解这种问题，”美国麻省理工学院综合性理论学家迈克尔·赛普泽说道，“先投出 100个点，每点表示一个人，然后在相应的彼此认识的两人的点之间划一直线。”于是你将希望这组的50个点全都有连线。赛普泽接着又说：“看起来它很像一个有关计算机方面的重大问题，然而它不是。我们知道，如何去解这种问题，仅有的一种方法实质上是查看50人小组的所有连线，它们的数量非常多，就像10的29次方。要解出这个问题，即使应用快速的计算机，也要好几百年。”

    旅行推销员的问题、人群问题、以及所有其他NP-完全的问题，都有难以理解的共同特点：如果有人声称，他对于这类问题中的任何一个特殊事例已经有了解法，那么要检验这个解法则是很容易的事。对于旅行推销员问题，只要检查所提出的旅程，并查明是否包括了每个城市一次。对于人群的问题，则要双向检查已被辨认全都互相认识而成群体的50个人。美国伯克利市加利福尼亚大学计算机科学教授理查德·卡普把 NP-完全的问题比作拼图玩具：“它们可能难于组合，但是当有人向你展示一幅完全的拼图时，你就能一下子知道问题已有正确解。”

    NP-完全的问题还有一个醒目的特点，如果这类问题中的任何一个问题能够用快速算法求解，那么其他问题也都能用此法解出。而且，对于某类NP-完全问题采用快速算法毫不费力，而且稍加改进，就可用于解任何其他NP-完全问题。例如，如果人们发现了一种用于解旅行推销员问题的快速算法，那么数学家们就会自如地运用快速方法去解人群问题和所有其他的NP-完全问题。因此，旅行推销员问题是否有快速解法与NP-完全问题是否真的像看上去那样难这一较大问题有关。

    美国电话电报公司的戴维·约翰逊说道：“我认为，现在每位数学家实际上都认为NP-完全问题有内在的困难。”约翰逊是这一领域的权威人士，著有《计算机和难处理性：NP-完全理论指南》一书。他还说：“真正的问题是证明它。”

    这种论点动摇了一些数学家的想法，他们认为他们也许能够证明旅行推销员问题及同类的其他问题都不会有快速解法——从来就没有过——即使未来让爱因斯坦一类大师来绞脑汁也不会有。他们怎么会提出要证明这样的问题？

    目前的工作都集中在逻辑门上，它已被认为是计算机硬件中最基本的单元。在电子计算机内，逻辑门是一种组件，由任意数目的输入引线与一根输出引线组成。逻辑门也是一种二进制器件：每根引线中的信号都被认为或是1、或是0。（在电子学术语中，高电平对应于1，低电平对应于0。）

    每一个逻辑门都能完成3种基本运算中的1种：“非”、“与”或“或”。这3种运算的名称都是根据布尔代数中已经使用的词“非”、“与”和“或”而得来的。布尔代数是19世纪40年代由乔治·布尔研究出来的一种开拓性的形式逻辑体系。布尔是一个贫穷补鞋匠的儿子，他自学数学，研究出符号逻辑体系，其中1表示真的，0表示假的。尽管布尔的研究工作使他获得了爱尔兰科克大学的数学教授职位，但直到100多年后第一部电子计算机问世之后，他的逻辑体系才得到数学界的完全赏识。

    在形式逻辑中（和日常的英语中），词“非”加在前面可把真语句变成假语句，而且反过来也一样。把它换成布尔代数的术