TC0

La classe de complexitat TC⁰ és usada en complexitat de circuits. És la primera classe de la jerarquia de les classes TC.

La classe TC⁰ conté tots els llenguatges que son decidibles per un circuit booleà amb profunditat constant i mida polinòmica, format només per portes AND, OR, NOT i majoria. Equivalentment, es poden usar portes de llindar enlloc de portes de majoria.

Aquesta classe conté problemes força importants, com el d'ordenar n nombres de n bits, multiplicar dos nombres de n bits, la divisió entera o reconèixer el llenguatge de Dyck amb dos tipus de parèntesis.

Relació amb d'altres classes

Es pot relacionar la classe TC⁰ amb altres classes de circuits, incloent AC⁰ i NC¹:

${\text{AC}}^0⊊{\text{AC}}^0[p]⊊{\text{TC}}^0\subseteq {\text{NC}}^1$

També és conegut que:

${\text{TC}}^0⊊\text{PP}$