History
Circuit complexity goes back to Shannon (1949), who proved that almost all Boolean functions on n variables require circuits of size Θ(2n/n). Despite this fact, complexity theorists were unable to prove circuit lower bounds for specific Boolean functions.
The first function for which superpolynomial circuit lower bounds could be shown was the parity function, which computes the sum of its input bits modulo 2. The fact that parity is not contained in AC0 was first established independently by Ajtai (1983) and by Furst, Saxe and Sipser (1984). Later improvements by Håstad (1987) in fact establish that any family of constant-depth circuits computing the parity function requires exponential size. 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 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 bits which indicate for each possible edge whether it is present. Then the k-clique problem is formalized as a function such that 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 Razborov (1985) was later improved to an exponential-size lower bound by Alon and Boppana (1987). Rossman (2008) shows that constant-depth circuits with AND, OR, and NOT gates require size to solve the k-clique problem even in the average case. Moreover, there is a circuit of size which computes .
Raz and McKenzie later showed that the monotone NC hierarchy is infinite (1999).
The Integer Division Problem lies in uniform TC0 (Hesse 2001).
Read more about this topic: Circuit Complexity
Famous quotes containing the word history:
“When the history of this period is written, [William Jennings] Bryan will stand out as one of the most remarkable men of his generation and one of the biggest political men of our country.”
—William Howard Taft (1857–1930)
“The foregoing generations beheld God and nature face to face; we, through their eyes. Why should not we also enjoy an original relation to the universe? Why should not we have a poetry and philosophy of insight and not of tradition, and a religion by revelation to us, and not the history of theirs?”
—Ralph Waldo Emerson (1803–1882)
“No one is ahead of his time, it is only that the particular variety of creating his time is the one that his contemporaries who are also creating their own time refuse to accept.... For a very long time everybody refuses and then almost without a pause almost everybody accepts. In the history of the refused in the arts and literature the rapidity of the change is always startling.”
—Gertrude Stein (1874–1946)