Circuit complexity: Difference between revisions

Revision as of 12:41, 28 February 2022

Revision as of 17:10, 8 May 2022

Line 32:

==History==

Circuit complexity goes back to [[Claude Shannon|Shannon]] in 1949,<ref name="Shannon_1949"/> who proved that almost all Boolean functions on ''n'' variables require circuits of size Θ(2^''n''/''n''). Despite this fact, complexity theorists have onlyso far been ableunable to prove [[Timea complexity#Superpolynomial time|superpolynomial]] circuitsuperlinear lower bounds on functions explicitly constructedbound for theany purpose of being hard toexplicit calculatefunction.

More commonly, superpolynomialSuperpolynomial lower bounds have been proved under certain restrictions on the family of circuits used. The first function for which superpolynomial circuit lower bounds were shown was the [[parity function]], which computes the sum of its input bits modulo 2. The fact that parity is not contained in [[AC0|AC⁰]] was first established independently by Ajtai in 1983<ref name="Ajtai_1983"/><ref name="Ajtai-Komlós-Szemerédi_1983"/> and by Furst, Saxe and Sipser in 1984.<ref name="Furst-Saxe-Sipser_1984"/> Later improvements by [[Johan Håstad|Håstad]] in 1987<ref name="Håstad_1987"/> established that any family of constant-depth circuits computing the parity function requires exponential size. Extending a result of Razborov,<ref name="Razborov_1985"/> Smolensky in 1987<ref name="Smolensky_1987"/> proved that this is true even if the circuit is augmented with gates computing the sum of its input bits modulo some odd prime ''p''.

The [[clique problem|''k''-clique problem]] is to decide whether a given graph on ''n'' vertices has a clique of size ''k''. For any particular choice of the constants ''n'' and ''k'', the graph can be encoded in binary using <math>{n \choose 2}</math> bits, which indicate for each possible edge whether it is present. Then the ''k''-clique problem is formalized as a function <math>f_k:\{0,1\}^{{n \choose 2}}\to\{0,1\}</math> such that <math>f_k</math> outputs 1 if and only if the graph encoded by the string contains a clique of size ''k''. This family of functions is monotone and can be computed by a family of circuits, but it has been shown that it cannot be computed by a polynomial-size family of monotone circuits (that is, circuits with AND and OR gates but without negation). The original result of [[Alexander Razborov|Razborov]] in 1985<ref name="Razborov_1985"/> was later improved to an exponential-size lower bound by Alon and Boppana in 1987.<ref name="Alon-Boppana_1987"/> In 2008, Rossman<ref name="Rossman_2008"/> showed that constant-depth circuits with AND, OR, and NOT gates require size <math>\Omega(n^{k/4})</math> to solve the ''k''-clique problem even in the [[average-case complexity|average case]]. Moreover, there is a circuit of size <math>n^{k/4+O(1)}</math> that computes <math>f_k</math>.