Lesson plan
TC (complexity)
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.
Article summary
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.
Key claims
No claims recorded.
Discussion questions
- Summarise the article in your own words. Which single claim would you verify first, and why?
- Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
- If two sources disagreed about one of these facts, what would you need in order to trust one over the other?
Bibliography
No sources recorded.
Key claims and bibliography are generated from the same tracked claims and sources as the article page.