Circuit complexity

In <a href="/facts/Theoretical_computer_science/jSkGGuvy">theoretical computer science</a>, circuit complexity is a branch of <a href="/facts/Computational_complexity_theory/etHuVF3U">computational complexity theory</a> in which <a href="/facts/Boolean_function/uT7E8pqC">Boolean functions</a> are classified according to the size or depth of the <a href="/facts/Boolean_circuit/TwhfJp0q">Boolean circuits</a> that compute them. A related notion is the circuit complexity of a <a href="/facts/Recursive_language/4R0zBWJE">recursive language</a> that is <a href="/facts/Machine_that_always_halts/lGTrkxDE">decided</a> by a uniform family of circuits 
 
 
 
 
 C
 
 1
 
 
 ,
 
 C
 
 2
 
 
 ,
 …
 
 
 {\displaystyle C_{1},C_{2},\ldots }
 
 (see below).
Proving lower bounds on size of Boolean circuits computing explicit Boolean functions is a popular approach to separating complexity classes. For example, a <a href="/facts/P%2fpoly/cHXNlnYJ">prominent</a> circuit class <a href="/facts/P%2fpoly/cHXNlnYJ">P/poly</a> consists of Boolean functions computable by circuits of polynomial size. Proving that 
 
 
 
 
 
 N
 P
 
 
 ⊈
 
 
 P
 
 /
 
 p
 o
 l
 y
 
 
 
 
 {\displaystyle {\mathsf {NP}}\not \subseteq {\mathsf {P/poly}}}
 
 would separate <a href="/facts/P_(complexity)/2TYvck4k">P</a> and <a href="/facts/NP_(complexity)/6muUfVMI">NP</a> (see below).
<a href="/facts/Complexity_class/IIKrcTbP">Complexity classes</a> defined in terms of Boolean circuits include <a href="/facts/AC0/UGJ79CeY">AC0</a>, <a href="/facts/AC_(complexity)/zL9RfPbm">AC</a>, <a href="/facts/TC0/bVAP8vqz">TC0</a>, <a href="/facts/NC1_(complexity)/4SY2L2Kg">NC1</a>, <a href="/facts/NC_(complexity)/4SY2L2Kg">NC</a>, and <a href="/facts/P%2fpoly/cHXNlnYJ">P/poly</a>.

Circuit complexity open-in-new

Circuit complexity