TC0
Complexity class used in circuit complexity / From Wikipedia, the free encyclopedia
Dear Wikiwand AI, let's keep it short by simply answering these key questions:
Can you list the top facts and stats about TC0?
Summarize this article for a 10 year old
SHOW ALL QUESTIONS
TC0 is a complexity class used in circuit complexity. It is the first class in the hierarchy of TC classes.
TC0 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 majority gates. Equivalently, threshold gates can be used instead of majority gates.
TC0 contains several important problems, such as sorting n n-bit numbers, multiplying two n-bit numbers, integer division[1] or recognizing the Dyck language with two types of parentheses.