Circuit complexity: Difference between revisions

Revision as of 17:38, 21 June 2020

Revision as of 17:41, 21 June 2020

Line 56:

Proofs of circuit lower bounds are strongly connected to [[derandomization]]. A proof that <math>\mathsf{P} = \mathsf{BPP}</math> would imply that either <math>\mathsf{NEXP} \not \subseteq \mathsf{P/poly}</math> or that permanent cannot be computed by nonuniform arithmetic circuits (polynomials) of polynomial size and polynomial degree.<ref>{{cite journal|last1=Kabanets|first1=V.|last2=Impagliazzo|first2=R.|journal=Computational Complexity|doi=10.1007/s00037-004-0182-6|title=Derandomizing polynomial identity tests means proving circuit lower bounds|pages=1–46|volume=13|number=1|year=2004}}</ref>

Razborov and Rudich (1997) showed that many known circuit lower bounds for explicit Boolean functions imply the existence of so called [[Natural proof|natural properties]] useful against the respective circuit class.<ref name="RazRu">{{cite news|first1=Alexander|last1=Razborov|first2=Stephen|last2=Rudich|title=Natural proofs|journal=Journal of Computer and System Sciences|volume=55|pages=24-35|year=1997|}}</ref> On the other hand, natural properties useful against P/poly would break strong pseudorandom generators. This is often interpreted as a ``natural proofs" barrier for proving strong circuit lower bounds for explicit Boolean functions. Carmosino, Impagliazzo, Kabanets and Kolokolova (2016) proved that natural properties can be also used to construct efficient learning algorithms.<ref name="CIKK">{{cite news|first1=Marco|last1=Carmosino|first2=Russell|last2=Impagliazzo|first3=Valentine|last3=Kabanets|first4=Antonina|last4=Kolokolova|title=Learning algorithms from natural proofs|journal=Computational Complexity Conference|year=2016|}}</ref>

==Complexity classes==