Mostra la font per a TC0

{{DISPLAYTITLE:TC<sup>0</sup>}}

La '''[[classe de complexitat]] TC<sup>0</sup>''' és usada en [[complexitat de circuits]]. És la primera classe de la jerarquia de les classes TC.<ref>{{Ref-publicació|cognom=Hesse|nom=William|cognom2=Allender|nom2=Eric|cognom3=Mix Barrington|nom3=David A.|article=Uniform constant-depth threshold circuits for division and iterated multiplication|publicació=Journal of Computer and System Sciences|url=https://linkinghub.elsevier.com/retrieve/pii/S0022000002000259|volum=65|exemplar=4|data=2002-12|pàgines=695–716|doi=10.1016/s0022-0000(02)00025-9|issn=0022-0000}}</ref><ref>{{Ref-llibre|cognom=Peter.|nom=Clote,|títol=Boolean functions and computation models|url=https://www.worldcat.org/oclc/46791075|data=2002|editorial=Springer|lloc=Berlín|isbn=3540594361}}</ref>

La classe TC<sup>0</sup> conté tots els llenguatges que son [[Problema de decisió|decidibles]] per un [[Àlgebra de Boole|circuit booleà]] amb profunditat constant i mida polinòmica, format només per portes [[Porta AND|AND]], [[Porta OR|OR]], [[Porta NOT|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<sup>0</sup> amb altres classes de circuits, incloent AC<sup>0</sup> i NC¹:<blockquote><math>{\mbox{AC}}^{0}\subsetneq {\mbox{AC}}^{0}[p]\subsetneq {\mbox{TC}}^{0}\subseteq {\mbox{NC}}^{1}</math></blockquote>També és conegut que:<blockquote><math> {\mbox{TC}}^{0}\subsetneq {\mbox{PP}}</math></blockquote>

== Referències ==
{{Referències}}

{{Classes de complexitat}}
{{Autoritat}}

[[Categoria:Classes de complexitat]]