Lesson plan

TC0

In theoretical computer science, and specifically computational complexity theory and circuit complexity, TC 0 (Threshold Circuit) is the first class in the hierarchy of TC classes. TC 0 contains all languages which are decided by Boolean circuits with constant depth and polynomial size, containing only unbounded fan-in AND gates, OR gates, NOT gates, and MAJ gates, or equivalently, threshold gates. TC 0 contains several important problems, such as sorting n n-bit numbers, multiplying two n-bit numbers, integer division or recognizing the Dyck language with multiple types of parentheses. It is commonly used to model the computational complexity of bounded-depth neural networks, and indeed, it was originally proposed for this purpose.

Back to article

Article summary

In theoretical computer science, and specifically computational complexity theory and circuit complexity, TC 0 (Threshold Circuit) is the first class in the hierarchy of TC classes. TC 0 contains all languages which are decided by Boolean circuits with constant depth and polynomial size, containing only unbounded fan-in AND gates, OR gates, NOT gates, and MAJ gates, or equivalently, threshold gates. TC 0 contains several important problems, such as sorting n n-bit numbers, multiplying two n-bit numbers, integer division or recognizing the Dyck language with multiple types of parentheses. It is commonly used to model the computational complexity of bounded-depth neural networks, and indeed, it was originally proposed for this purpose.

Key claims

No claims recorded.

Discussion questions

  1. Summarise the article in your own words. Which single claim would you verify first, and why?
  2. Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
  3. 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.