语，则是“非”可把1转换为0，0转换为1。因此，“非”逻辑门有一根输入引线，并把输入信号转变为其相反信号，即如果输入是1，则输为0，而如果输入为0，则输出就为1。

    当然，词“与”用于连接单个语句成为复合语句，即如果每个组元都是真的，那么复合组元也是真的。现举一简单例子，“朱尔斯吃豆腐与吉姆吃多夫条形面包”，只有当朱尔斯和吉姆两个人都在吃上述的食物时，它才是一个真实语句。由于同样的理由，“与”门可接受两个或多个信号输入，如果所有的输入都是1时，那么输出也是1，否则，则输出为0。

    词“或”也是用于连接语句成为复合语句，但只要一个或几个组元都是真的，则其复合组元也是真的。如果朱尔斯或者吉姆（或者他们两人）在吃他们各自的食物，那么“朱尔斯吃豆腐或吉姆吃多夫条形面包”才是真语句。同样地，“或”门可以接受两个或几个信号输入，但只要至少输入之一是1时，则其输出也是1。

    布尔代数的绝妙之处在于，1和0不仅表示真的和假的，而且还可以表示任何两种不同的状态。例如在旅行推销员问题中，0和1可以表示城市之间的相应关系：如果两个城市由一条公路连接，则以1表示，如果它们没有公路连接，则以0表示。在人群的问题中，1可以表示两个人成为朋友的状态（或者在该问题的图解表示法中，表示由一条线连接的两点），0表示他们不是朋友的状态（表示没有线连接的两点）。

    在计算机中，任何数目的“与”门、“或”门和“非”门都可以连接在一起，形成一种电路。例如下图示出4个“与”门和1个“或”门组成的一种小型电路，它可以用来求解人群问题的普通实例：在4个人的一组中，有3个人是朋友吗？

    然而，随着人群问题的人数增加，用于已知解法的电路大小（也是逻辑门的数目）将按指数方式激增。如果数学家们能够证明，对于任何可能已知或未知解法，电路必按指数方式增大，那么他们就能证明人群问题没有快速算法。

    数学家们还不知道如何开始这样的证明，已经转而考虑另一特殊的问题，这就是通常都有快速算法的奇偶函数，而且他们还试图以某些基本方式来限制电路，使得快速算法不再产生作用。（奇偶函数可在一串的0与1中确定是否产生偶数或奇数。）这种方法看来也许有些怪，其实它并不怪。数学家们对于如何证明电路必须是大型的了解甚少，因此为此目的而做的任何证明，甚至是某种人为的情况，也都将会有所进展，而且可以提供证明真正论点所需的数学工具。赛普泽说道：“这是数学中的普通方法。如果问题很大，可试图把它限制到某些范围，并求解其中一部分，希望这种分部解法使人们对原来的问题会有更深的了解。”

    在这一领域内，早期的工作限制了电路的研究工作的深度，这里的深度是指逻辑门的层次数目。1981年取得了第一批成果，当时美国卡内基-梅隆大学的赛普泽及其两位同事证明了，如果他们限制用于奇偶函数的电路深度，那么电路宽度的扩展快于任何多项式。1985年，美国斯坦福大学的安德鲁·姚在这方面取得了更惊人的研究成果，他证明了电路的宽度不仅以超多项式的方式扩展，而且还以指数的方式扩展，这表明这种问题虽然受到人为的限制，但也有内在的困难。

    姚的成果很快地传遍了数学界。赛普泽这样说道：“每个人都认为这个结果很满意，但也是非常复杂的。”姚的方法为他人铺平了道路，好几个研究人员很快地对他的结果做了改进。美国电话电报公司贝尔实验室数学科学部主任罗纳德·格雷厄姆说：“这很像开车的头4分钟路程，一旦有人学会它，那么人人都可以学会它。”

    1985年8月，美国麻省理工学院计算机学科研究生约