Circuit Lower Bounds
Circuit lower bounds are generally difficult. Known results include
- Parity is not in nonuniform AC0, proved by Ajtai (1983) and by Furst, Saxe and Sipser.
- Uniform TC0 is not contained in PP, proved by Allender.
- The classes SP
2, PP and MA/1 (MA with one bit of advice) are not in SIZE(nk) for any constant k. - While it is suspected that the nonuniform class ACC0 does not contain the majority function, it was only in 2010 that Williams proved that .
It is open whether NEXPTIME has nonuniform TC0 circuits.
Proofs of circuit lower bounds are strongly connected to derandomization. A proof that P = BPP would imply that either or that permanent cannot be computed by nonuniform arithmetic circuits (polynomials) of polynomial size and polynomial degree.
Read more about this topic: Circuit Complexity
Famous quotes containing the words circuit and/or bounds:
“each new victim treads unfalteringly
The never altered circuit of his fate,
Bringing twelve peers as witness
Both to his starry rise and starry fall.”
—Robert Graves (1895–1985)
“Prohibition will work great injury to the cause of temperance. It is a species of intemperance within itself, for it goes beyond the bounds of reason in that it attempts to control a man’s appetite by legislation, and makes a crime out of things that are not crimes. A Prohibition law strikes a blow at the very principles upon which our government was founded.”
—Abraham Lincoln (1809–1865)