Content deleted Content added
Added a section on monotone circuits |
mNo edit summary |
||
Line 61:
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>{{cite journal|first1=Nicholas|last1=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|s2cid=2432526 |doi-access=free}}
</ref>
==Monotone circuits==
| |||