TC0

In <a href="/facts/Theoretical_computer_science/jSkGGuvy">theoretical computer science</a>, and specifically <a href="/facts/Computational_complexity_theory/etHuVF3U">computational complexity theory</a> and <a href="/facts/Circuit_complexity/6EzA9Tty">circuit complexity</a>, TC0 (Threshold Circuit) is the first class in the hierarchy of <a href="/facts/TC_(complexity)/NErc3ef7">TC</a> classes. TC0 contains all languages which are decided by <a href="/facts/Boolean_circuit/TwhfJp0q">Boolean circuits</a> with constant depth and polynomial size, containing only unbounded fan-in <a href="/facts/AND_gate/tVKQD0w1">AND gates</a>, <a href="/facts/OR_gate/ox2lHgIM">OR gates</a>, <a href="/facts/NOT_gate/pGk3qGTI">NOT gates</a>, and <a href="/facts/Majority_gate/Ntpb4wDr">MAJ gates</a>, or equivalently, <a href="/facts/Linear_threshold_unit/TSH6nsgg">threshold gates</a>.
TC0 contains several important problems, such as sorting n n-bit numbers, multiplying two n-bit numbers, integer division or recognizing the <a href="/facts/Dyck_language/L3ro6dWp">Dyck language</a> with two types of parentheses. It is commonly used to model the computational complexity of bounded-depth <a href="/facts/Neural_network_(machine_learning)/6V1jMlkx">neural networks</a>, and indeed, it was originally proposed for this purpose.

TC0 open-in-new

TC0