電路複雜性
![]() |
電路複雜性理論在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的前景表示不樂觀。
分支程序
分支程序是電路複雜性的一個研究方向。
算術電路複雜性
算術電路某種程度上可以看作布爾電路的代數版本。與布爾電路計算一個布爾函數不同,它計算的是一個在一個特定域上的多項式。