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)
“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)