电路复杂性 电路复杂性理论在年代以前被众多研究者认为是解决NP与P关系问题的可能的途径之一电路复杂性研究的对象是非一致性的计算模型电路并考虑计算一个布尔函数所需的最小的电路的深度depth和大小size等资源其中大小为多项式大小的电路族可以计算的布尔函数被记为Ppoly可以证明P包含在Ppoly之中而卡普利普顿定理KarpLipton theorem表明若Ppoly在NP之中则多项式层级polynomial hierarchy将会坍缩至第二层这是一个不大可能的结果这两个结果结合起来表明Ppoly可以当作是分离NP与P的一个中间的工具具体的途径就是证明任一个NP完全问题的电路大小的下界在直观上说电路复杂性也绕过了NP与P问题的第一个困难相对化证明困难relativizing proofs 在年代电路复杂性途径取得了一系列的成功其中包括奇偶性函数Parity function在 A C  displaystyle AC 中的下界为指数以及团问题clique problem在单调性电路monotone circuit中的下界为指数然而在年Alexander Razborov英语Alexander Razborov和Steven Rudich英语Steven Rudich的著名论文自然性证明Natural proof中指出上面所用证明电路下界的方法在单向函数存在的前提下是不可能分离NP和P的该结果使很多专家对证明电路下界来分离NP和P的前景表示不乐观