TC0

La classe de complexitat TC⁰ és usada en complexitat de circuits. És la primera classe de la jerarquia de les classes TC.^[1][2]

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

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

També és conegut que:

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

Referències

1. Hesse, William; Allender, Eric; Mix Barrington, David A. «Uniform constant-depth threshold circuits for division and iterated multiplication». Journal of Computer and System Sciences, 65, 4, 12-2002, pàg. 695–716. DOI: 10.1016/s0022-0000(02)00025-9. ISSN: 0022-0000.
2. Peter., Clote,. Boolean functions and computation models. Berlín: Springer, 2002. ISBN 3540594361.