Editing Clique problem (section)

===Circuit complexity===
[[File:Monotone circuit for 3-clique.svg|thumb|A monotone circuit to detect a {{mvar|k}}-clique in an {{mvar|n}}-vertex graph for {{math|1=''k''&nbsp;=&nbsp;3}} and {{math|1=''n''&nbsp;=&nbsp;4}}. Each input to the circuit encodes the presence or absence of a particular (red) edge in the graph. The circuit uses one internal and-gate to detect each potential {{mvar|k}}-clique.]]
The computational difficulty of the clique problem has led it to be used to prove several lower bounds in [[circuit complexity]]. The existence of a clique of a given size is a [[Hereditary property|monotone graph property]], meaning that, if a clique exists in a given graph, it will exist in any [[Glossary of graph theory terms#supergraph|supergraph]]. Because this property is monotone, there must exist a monotone circuit, using only [[and gate]]s and [[or gate]]s, to solve the clique decision problem for a given fixed clique size. However, the size of these circuits can be proven to be a super-polynomial function of the number of vertices and the clique size, exponential in the cube root of the number of vertices.<ref>{{harvtxt|Alon|Boppana|1987}}. For earlier and weaker bounds on monotone circuits for the clique problem, see {{harvtxt|Valiant|1983}} and {{harvtxt|Razborov|1985}}.</ref> Even if a small number of [[NOT gate]]s are allowed, the complexity remains superpolynomial.<ref>{{harvtxt|Amano|Maruoka|2005}}.</ref> Additionally, the depth of a monotone circuit for the clique problem using gates of bounded [[fan-in]] must be at least a polynomial in the clique size.<ref>{{harvtxt|Goldmann|Håstad|1992}} used [[communication complexity]] to prove this result.</ref>