Content deleted Content added
m Open access bot: doi updated in citation with #oabot. |
Added a section on monotone circuits |
||
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==
A monotone Boolean circuit is one that has only AND and OR gates, but no NOT gates. A monotone circuit can only compute a monotone Boolean function, which is a function <math>f:\{0,1\}^n \to \{0,1\}</math> where for every <math>x,y \in \{0,1\}^n</math>, <math>x \leq y \implies f(x) \leq f(y)</math>, where <math>x\leq y</math> means that <math>x_i \leq y_i</math> for all <math>i \in \{1,\ldots,n\}</math>.
==See also==
| |||