TC0

---

TC ⁰ es una clase de complejidad utilizada en la complejidad de circuitos . Es la primera clase en la jerarquía de clases de TC .

TC ⁰ contiene todos los lenguajes que se deciden mediante circuitos booleanos con profundidad constante y tamaño polinomial, que contienen solo puertas Y de entrada de abanico ilimitadas , puertas OR , puertas NO y puertas de mayoría . De manera equivalente, se pueden usar puertas de umbral en lugar de puertas de mayoría.

TC ⁰ contiene varios problemas importantes, como clasificar n números de n bits, multiplicar dos números de n bits, dividir enteros ^[1] o reconocer el lenguaje Dyck con dos tipos de paréntesis.

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

Vollmer afirma que la cuestión de si la última inclusión anterior es estricta es "uno de los principales problemas abiertos en la complejidad del circuito" (ibid.).

También tenemos ese uniforme . (Allender 1996, citado en Burtschick 1999).${\ displaystyle {\ mathsf {TC}} ^ {0} \ subsetneq {\ mathsf {PP}}}$

---