Circuit complexity: Difference between revisions

Revision as of 09:39, 22 June 2020

Revision as of 21:52, 13 January 2021

Line 49:

* Parity is not in nonuniform [[AC0|AC⁰]], proved by Ajtai (1983) and by Furst, Saxe and Sipser.

* Uniform [[TC0|TC⁰]] 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|booktitlebook-title=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^k) for any constant k.

* While it is suspected that the nonuniform class [[ACC0|ACC⁰]] 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|booktitlebook-title=CCC 2011: Proceedings of the 26th Annual IEEE Conference on Computational Complexity|pages=115–125}}</ref>}}

It is open whether NEXPTIME has nonuniform TC⁰ circuits.

Line 69:

==References==

*{{cite journal|first=Miklós|last=Ajtai|authorlinkauthor-link=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|doi=10.1016/0168-0072(83)90038-6}}

*{{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|doi=10.1007/bf02579196|citeseerx=10.1.1.300.9623}}

*{{cite journal|first1=Merrick L.|last1=Furst|first2=James B.|last2=Saxe|first3=Michael|last3=Sipser|title=Parity, circuits, and the polynomial-time hierarchy|journal=Mathematical Systems Theory|volume=17|number=1|pages=13–27|year=1984|doi=10.1007/bf01744431}}

*{{citation|first=Johan|last=Håstad|title=Computational limitations of small depth circuits|year=1987|publisher=Ph.D. thesis, Massachusetts Institute of Technology|url=http://www.nada.kth.se/~johanh/thesis.pdf|postscript=.}}

*{{cite conference|first=William|last=Hesse|title=Division is in uniform TC⁰|year=2001|pages=104–114|booktitlebook-title=Proc. 28th International Colloquium on Automata, Languages and Programming|publisher=Springer}}

*{{cite journal|first1=Ran|last1=Raz|first2=Pierre|last2=McKenzie|title=Separation of the monotone NC hierarchy|journal=Combinatorica|volume=19|number=3|year=1999|pages=403–435|doi=10.1007/s004930050062}}

*{{cite journal|first=Alexander A.|last=Razborov|authorlinkauthor-link=Alexander Razborov|title=Lower bounds on the monotone complexity of some Boolean functions|year=1985|journal=Mathematics of the USSR, Doklady|volume=31|pages=354–357}}

*{{cite conference|first=Benjamin|last=Rossman|title=On the constant-depth complexity of k-clique|year=2008|pages=721–730|booktitlebook-title=STOC 2008: Proceedings of the 40th annual ACM symposium on Theory of computing|publisher=ACM|doi=10.1145/1374376.1374480}}

*{{cite journal|last=Shannon|first=Claude E.|authorlinkauthor-link=Claude Shannon|title=The synthesis of two-terminal switching circuits|journal=Bell System Technical Journal|year=1949|volume=28|number=1|pages=59–98|doi=10.1002/j.1538-7305.1949.tb03624.x}}

*{{cite conference|first=Roman|last=Smolensky|title = Algebraic methods in the theory of lower bounds for Boolean circuit complexity|year=1987|pages=77–82|booktitlebook-title=Proc. 19th Annual ACM Symposium on Theory of Computing|publisher=ACM|doi=10.1145/28395.28404}}

*{{cite book|title=Introduction to Circuit Complexity: a Uniform Approach|last=Vollmer|first=Heribert|publisher=[[Springer Verlag]]|year=1999|isbn=978-3-540-64310-4}}

*{{cite book

|last = Wegener

|first = Ingo

|authorlinkauthor-link = Ingo Wegener

|title = The Complexity of Boolean Functions

|publisher = John Wiley and Sons Ltd, and B. G. Teubner, Stuttgart