Encyclopedia

TC (complexity)

Wikipedia contributorsAdapted for Fathomly · View authors

1 min read
Source updated August 27, 2026

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ⁱ 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.

01Relation 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⁰ cannot compute any function that depends on all the input bits. Thus choosing a problem that is trivially in AC⁰ and depends on all bits separates the two classes. (For example, consider the OR function.) The strict containment AC⁰ ⊊ TC⁰ follows because parity and majority (which are both in TC⁰) were shown to be not in AC⁰.

As an immediate consequence of the above containments, we have that NC = AC = TC.

Watch videos about TC (complexity)Explainers and documentaries on YouTube (opens in a new tab)

Sources and credits

This article is adapted from the Wikipedia article “TC (complexity)”, written by its contributors and licensed under CC BY-SA 4.0. Fathomly has changed the layout, removed citation markers, navigation and maintenance notices, and adjusted punctuation. This adapted version is shared under the same license. For references, see the original article.

Fathomly is not affiliated with or endorsed by the Wikimedia Foundation. Spotted a problem? Tell us.