Circuit complexity: Difference between revisions

Revision as of 17:17, 29 January 2023

Revision as of 18:45, 7 July 2023

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{O}(t(n))</math>.<ref>{{Citationcite journal|first=Nicholas|last=Pippenger|authorlink=Nick Pippenger|first2=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>