電路複雜性
電路複雜性理論在1990年代以前，被眾多研究者認為是解決NP與P關係問題的可能的途徑之一。電路複雜性研究的對象是非一致性的計算模型電路，並考慮計算一個布爾函數所需的最小的電路的深度（depth）和大小（size）等資源。其中，大小為多項式大小的電路族可以計算的布爾函數被記為P/poly。可以證明，P包含在P/poly之中，而卡普-利普頓定理（Karp-Lipton theorem）表明若P/poly在NP之中，則多項式層級（polynomial hierarchy）將會坍縮至第二層，這是一個不大可能的結果。這兩個結果結合起來表明，P/poly可以當作是分離NP與P的一個中間的工具，具體的途徑就是證明任一個NP完全問題的電路大小的下界。在直觀上說，電路複雜性也繞過了NP與P問題的第一個困難：相對化證明困難（relativizing proofs）。
在1980年代，電路複雜性途逕取得了一系列的成功，其中包括奇偶性函數（Parity function）在中的下界為指數，以及團問題（clique problem）在單調性電路（monotone circuit）中的下界為指數。然而在1994年Alexander Razborov和Steven Rudich的著名論文自然性證明（Natural proof）中指出，上面所用證明電路下界的方法，在單向函數存在的前提下是不可能分離NP和P的。該結果使很多專家對證明電路下界來分離NP和P的前景表示不樂觀。
分支程序 編輯
分支程序是電路複雜性的一個研究方向。
算術電路複雜性 編輯
算術電路某種程度上可以看作布爾電路的代數版本。與布爾電路計算一個布爾函數不同，它計算的是一個在一個特定域上的多項式。