Content deleted Content added
Line 47:
* Uniform [[TC0|TC<sup>0</sup>]] is strictly 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>{{cite conference|last=Santhanam|first=Rahul|url=http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.111.1811|title=Circuit lower bounds for Merlin-Arthur classes|booktitle=STOC 2007: Proceedings of the thirty-ninth annual ACM symposium on Theory of computing|year=2007|pages=275–283|doi=10.1145/1250790.1250832|citeseerx=10.1.1.92.4422}}</ref> (MA with one bit of advice) are not in '''SIZE'''(n<sup>k</sup>) for any constant k.
* While it is suspected that the nonuniform class [[ACC0|ACC<sup>0</sup>]] does not contain the majority function, it was only in 2010 that [[Ryan Williams (computer scientist)|Williams]] proved that {{nowrap|<math>\mathsf{NEXP} \not \subseteq \mathsf{ACC}^0</math>.<ref>{{cite conference|last=Williams|first=Ryan|title=Non-Uniform ACC Circuit Lower Bounds|url=http://www.stanford.edu/~rrwill/acc-lbs.pdf|doi=10.1109/CCC.2011.36|year=2011|booktitle=CCC 2011: Proceedings of the 26th Annual IEEE Conference on Computational Complexity|pages=115–125}}</ref>}}
It is open whether NEXPTIME has nonuniform TC<sup>0</sup> circuits.
| |||