TC (Complexity)

The threshold-circuit complexity hierarchy whose level TC^i contains languages decided by polynomial-size, unbounded-fan-in Boolean circuit families of depth O(log^i n) with threshold or majority gates, and whose union over fixed i is TC.

Version

v1 · 2026-09-28 · History

Domain-specific #

12469

Domain group

Applied Sciences & Engineering

Origin domain

Computer Science & Software Engineering

Subdomains

Circuit Complexity, Computational Complexity Theory → Computer Science & Software Engineering

Aliases

Threshold Circuit Complexity, TC Hierarchy

Core Idea

TC measures what polynomially many threshold gates can compute in shallow parallel layers. Majority makes the model stronger than AND/OR-only constant-depth circuits while still constraining global circuit size and depth.

The notation is incomplete without a level and uniformity convention. Constant-depth TC^0, polylogarithmic levels, and their union support different statements, and a nonuniform circuit family is not automatically an algorithm.

Scope of Application

• Circuit complexity. Compares shallow gate families.
• Parallel algorithms. Relates circuits to highly parallel computation.
• Lower bounds. Studies separations among AC, TC, NC, and related classes.
• Arithmetic and neural models. Uses threshold gates under discrete resource controls.

Clarity

State TC or TC^i, gate basis, weighted versus majority thresholds, fan-in, size measure, depth bound, weight encoding, uniform or nonuniform convention, language/promise definition, and reduction or containment notion. Inclusion test: Require a language decided by a circuit family meeting the stated threshold-gate basis, polynomial-size, fan-in, depth, and uniformity conditions for TC or a named level. Exclusion test: Exclude threshold decision policies unrelated to circuits, neural networks with unrestricted real weights called TC by analogy, AC circuits lacking majority gates when the distinction matters, and the topological symbol T_c. Nearest boundary: TC^0 is constant-depth threshold circuitry; TC without a superscript is the union over fixed polylogarithmic-depth levels under the selected uniformity convention. Exit condition: Membership or separation claims change when weights, gate basis, fan-in, depth, size, promise, or uniformity are altered. Common misclassifications: TC is not one circuit. Threshold gates do not mean unconstrained real-valued neural computation. TC^0 is not the same as AC^0. Membership claims need a uniformity convention when algorithmic meaning matters. Nearest named distinctions: AC: Uses unbounded fan-in AND/OR without threshold gates. NC: Uses bounded fan-in and polylogarithmic depth. Neural-network complexity: Can use different numeric precision and training assumptions. Turing complexity class TC: There is no standard identification with a same-named machine class absent circuit definition.

Manages Complexity

A few resource parameters separate strikingly different models. Global majority at shallow depth captures arithmetic structure that AND/OR circuits cannot, while uniformity determines whether the family is computationally describable.

Abstract Reasoning

1. Define the decision language and one circuit per input length.
2. Fix gate basis, fan-in, size, depth exponent, and weight representation.
3. Declare and verify the circuit-family uniformity condition.
4. Construct the family or reduce to a known TC-complete/membership result.
5. Compare containments only at matching level and convention.

Knowledge Transfer

Threshold-circuit techniques transfer to parallel arithmetic and discrete neural abstractions when Boolean resources are preserved. Real-valued learning systems or physical hardware need an explicit translation before TC results apply.

Relationships to Other Abstractions

Current abstraction TC (Complexity) Domain-specific

Parents (1) — more general patterns this builds on

• TC (Complexity) is a kind of Complexity Class Domain-specific

  TC (Complexity) is a strict kind of Complexity Class: its frozen identity entails the parent's defining structure while adding domain-specific restrictions.

Hierarchy paths (6) — routes to 5 parentless roots

• TC (Complexity) → Complexity Class → Classification

Show alternative paths (5)

Neighborhood in Abstraction Space

TC (Complexity) sits in a crowded region of the domain-specific corpus (36^th percentile for distinctiveness): several abstractions share nearly its structure, so a description that fits it tends to fit its neighbors too.

Family — Digital Logic & Finite-State Machines (10 abstractions)

Nearest neighbors

• Switching circuit theory — 0.89
• Exact Quantum Polynomial Time — 0.89
• NOR logic — 0.88
• NEXPTIME — 0.88
• Random Quantum Circuit — 0.87

Computed from structural-signature embeddings · 2026-10-08