TC0

Laclasse de complexitatTC⁰és usada encomplexitat de circuits.És la primera classe de la jerarquia de les classes TC.

La classe TC⁰conté tots els llenguatges que sondecidiblesper uncircuit booleàamb profunditat constant i mida polinòmica, format només per portesAND,OR,NOTi majoria. Equivalentment, es poden usar portes de llindar enlloc de portes de majoria.

Aquesta classe conté problemes força importants, com el d'ordenarnnombres denbits, multiplicar dos nombres denbits, 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}}$