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¹:

${\mbox{AC}}^{0}\subsetneq {\mbox{AC}}^{0}[p]\subsetneq {\mbox{TC}}^{0}\subseteq {\mbox{NC}}^{1}$

També és conegut que:

${\mbox{TC}}^{0}\subsetneq {\mbox{PP}}$