查看“︁电路复杂性”︁的源代码

{{多個問題|
{{expand|time=2009-07-29T01:45:45+00:00}}
{{unreferenced|time=2009-07-29T01:45:45+00:00}}
}}
'''电路复杂性'''理论在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）在<math>AC^0</math>中的下界为指数，以及[[团问题]]（clique problem）在[[单调性电路]]（monotone circuit）中的下界为指数。然而在1994年{{le|Alexander Razborov}}和{{le|Steven Rudich}}的著名论文[[自然性证明]]（Natural proof）中指出，上面所用证明电路下界的方法，在[[单向函数]]存在的前提下是不可能分离NP和P的。该结果使很多专家对证明电路下界来分离NP和P的前景表示不乐观。

== 分支程序 ==
[[分支程序]]是电路复杂性的一个研究方向。

== 算术电路复杂性 ==

{{main|算术电路复杂性}}

[[算术电路 (复杂性)|算术电路]]某种程度上可以看作布尔电路的代数版本。与布尔电路计算一个布尔函数不同，它计算的是一个在一个特定域上的多项式。

[[Category:計算複雜性理論]]