Content deleted Content added
circuit lower bounds |
|||
Line 32:
The Integer Division Problem lies in uniform [[TC0|TC<sup>0</sup>]] (Hesse 2001).
==Circuit lower bounds==
Circuit lower bounds are generally difficult. Known results include
* 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.
* 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>.
It is open whether NEXPTIME has nonuniform TC<sup>0</sup> circuits.
Proofs of circuit lower bounds are strongly connected to [[derandomization]]. A proof that '''P''' = '''BPP''' would imply that either <math>\mathsf{NEXP} \not \subseteq \mathsf{P/poly}</math> or that permanent can be computed by nonuniform algebraic circuits (polynomials) of polynomial size and polynomial degree.
==Complexity classes==
| |||