TC (complexity)
≈ 2 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
In theoretical computer science, and specifically computational complexity theory and circuit complexity, TC (Threshold Circuit) is a complexity class of decision problems that can be recognized by threshold circuits, which are Boolean circuits with AND, OR, and Majority gates, or equivalently, threshold gates. For each fixed i, the complexity class TC i consists of all languages that can be recognized by a family of threshold circuits of depth O(\log^i n) , polynomial size, and unbounded fan-in. The class TC is defined via : \mbox{TC} = \bigcup_{i \geq 0} \mbox{TC}^i. The class was proposed in 1988 to formalize the computational complexity of artificial neural networks.
In theoretical computer science, and specifically computational complexity theory and circuit complexity, TC (Threshold Circuit) is a complexity class of decision problems that can be recognized by threshold circuits, which are Boolean circuits with AND, OR, and Majority gates, or equivalently, threshold gates. For each fixed i, the complexity class TC i consists of all languages that can be recognized by a family of threshold circuits of depth O(\log^i n) , polynomial size, and unbounded fan-in. The class TC is defined via \mbox{TC} = \bigcup_{i \geq 0} \mbox{TC}^i. The class was proposed in 1988 to formalize the computational complexity of artificial neural networks. ==Relation to NC and AC== The relationship between the TC, NC and the AC hierarchy can be summarized as follows: \mbox{NC}^i \subseteq \mbox{AC}^i \subseteq \mbox{TC}^i \subseteq \mbox{NC}^{i+1}. In particular, we know that \mbox{NC}^0 \subsetneq \mbox{AC}^0 \subsetneq \mbox{TC}^0 \subseteq \mbox{NC}^{1}. The first strict containment follows from the fact that NC 0 cannot compute any function that depends on all the input bits. Thus choosing a problem that is trivially in AC 0 and depends on all bits separates the two classes. (For example, consider the OR function.) The strict containment AC 0 ⊊ TC 0 follows because parity and majority (which are both in TC 0 ) were shown to be not in AC 0 . As an immediate consequence of the above containments, we have that NC = AC = TC. ==References==
Text derived from https://en.wikipedia.org/w/index.php?oldid=1371586664 under CC BY-SA 4.0; modifications have been made.