Content deleted Content added
m →top: \mathsf |
m →Circuit lower bounds: fix math italic |
||
Line 46:
* Parity is not in nonuniform [[AC0|AC<sup>0</sup>]], proved by Ajtai in 1983<ref name="Ajtai_1983"/><ref name="Ajtai-Komlós-Szemerédi_1983"/> as well as by Furst, Saxe and Sipser in 1984.<ref name="Furst-Saxe-Sipser_1984"/>
* Uniform [[TC0|TC<sup>0</sup>]] is strictly contained in [[PP (complexity)|PP]], proved by Allender.<ref name="Allender_1997"/>
* The classes [[S2P (complexity)|S{{su|p=P|b=2}}]], PP<ref group="nb" name="NB1"/> and [[MA (complexity)|MA]]/1<ref name="Santhanam_2007"/> (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 name="Williams_2011"/>}}
| |||