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:
“Within the circuit of this plodding life
There enter moments of an azure hue,
Untarnished fair as is the violet
Or anemone, when the spring strews them
By some meandering rivulet, which make
The best philosophy untrue that aims
But to console man for his grievances.
I have remembered when the winter came,”
—Henry David Thoreau (1817–1862)
“Great Wits are sure to Madness near alli’d
And thin Partitions do their Bounds divide;
Else, why should he, with Wealth and Honour blest,
Refuse his Age the needful hours of Rest?”
—John Dryden (1631–1700)