Content deleted Content added
circuit lower bounds |
No edit summary |
||
Line 37:
* Parity is not in nonuniform [[AC0|AC<sup>0</sup>]], proved by Ajtai (1983) and by Furst, Saxe and Sipser.
* Uniform [[TC0|TC<sup>0</sup>]] is not contained in [[PP (complexity)|PP]], proved by Allender.
* The classes [[S2P (complexity)|S{{su|p=P|b=2}}]], PP<ref>See [[Karp-Lipton theorem#Application for circuit lower bounds - Kannan's theorem|proof]]</ref> and [[MA (complexity)|MA]]/1<ref>R. Santhanam. [http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.111.1811 Circuit lower bounds for Merlin-Arthur classes]</ref> (MA with one bit of advice) are not in '''SIZE'''(n<sup>k</sup>) for any constant k.
* While it is suspected that nonuniform [[ACC0|ACC<sup>0</sup>]] class doesn't contain majority function, only in 2010 it has been proved by [[Ryan Williams (computer scientist)|Ryan Williams]] that <math>\mathsf{NEXP} \not \subseteq \mathsf{ACC}^0</math>.
Line 51 ⟶ 52:
==References==
{{reflist}}
*{{cite journal|first=Miklós|last=Ajtai|authorlink=Miklós Ajtai|title=<math>\Sigma^1_1</math>-formulae on finite structures|journal=Annals of Pure and Applied Logic|year=1983|volume=24|pages=1–24}}
*{{cite journal|first1=Noga|last1=Alon|first2=Ravi B.|last2=Boppana|title=The monotone circuit complexity of Boolean functions|journal=Combinatorica|volume=7|year=1987|number=1|pages=1–22}}
| |||