Circuit complexity: Difference between revisions

Revision as of 02:13, 6 July 2021

Revision as of 22:01, 10 December 2021

Line 59:

==Relation to time complexity==

If a certain language, <math>A</math>, belongs to the [[Complexity class|time-complexity class]] <math>\text{TIME}(t(n))</math> for some function <math>t:\mathbb{N}\to\mathbb{N}</math>, then <math>A</math> has circuit complexity <math>\mathcal{O}(t^(n) \log t(n))</math>. If the Turing Machine that accepts the language is [[Turing machine equivalents|oblivious]] (meaning that it reads and writes the same memory cells regardless of input), then <math>A</math> has circuit complexity <math>\mathcal{2O}(t(n))</math>.<ref>{{Citation|first=Nicholas|last=Pippenger|authorlink=Nick namePippenger|first2="Sipser_1997"Michael J.|last2=Fischer|authorlink2=Michael J. Fischer|title=Relations Among Complexity Measures|journal=[[Journal of the ACM]]|year=1979|volume=26|issue=3|pages=361–381|doi=10.1145/>322123.322138}}

</ref>

==See also==