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:
“We are all hostages, and we are all terrorists. This circuit has replaced that other one of masters and slaves, the dominating and the dominated, the exploiters and the exploited.... It is worse than the one it replaces, but at least it liberates us from liberal nostalgia and the ruses of history.”
—Jean Baudrillard (b. 1929)
“At bounds of boundless void.”
—Samuel Beckett (1906–1989)