TC0

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

TC ⁰ contiene todos los lenguajes que se deciden mediante circuitos booleanos con profundidad constante y tamaño polinomial, que contienen solo puertas AND , puertas OR , puertas NOT y puertas mayoritarias sin límites . De manera equivalente, se pueden utilizar puertas de umbral en lugar de puertas mayoritarias.

TC ⁰ contiene varios problemas importantes, como ordenar 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.

Podemos relacionar TC ⁰ con otras clases de circuitos, incluidos AC ⁰ y NC ¹ ; Vollmer 1999 p. 126 afirma:

${\displaystyle {\mathsf {CA}}^{0}\subsetneq {\mathsf {CA}}^{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}}}$

La versión funcional del uniforme coincide con el cierre respecto a la composición de las proyecciones y uno de los siguientes conjuntos de funciones , . ^[2] Aquí , es un AND bit a bit de y . Por versión funcional se entiende el conjunto de todas las funciones sobre números enteros no negativos que están acotadas por funciones de FP y está en el uniforme . ${\displaystyle {\mbox{TC}}^{0}}$${\displaystyle \{n+m,n\,{\stackrel {.}{-}}\,m,n\wedge m,\lfloor n/m\rfloor ,2^{\lfloor \log _{2}n\rfloor ^{2}}\}}$${\displaystyle \{n+m,n\,{\stackrel {.}{-}}\,m,n\wedge m,\lfloor n/m\rfloor ,n^{\lfloor \log _{2}m\rfloor }\}}$${\displaystyle n\,{\stackrel {.}{-}}\,m=\max(0,nm)}$${\displaystyle n\cuña m}$${\estilo de visualización n}$${\estilo de visualización m}$${\displaystyle f(x_{1},\ldots ,x_{n})}$${\displaystyle (y{\text{-ésimo bit de }}f(x_{1},\ldots ,x_{n}))}$${\displaystyle {\mbox{TC}}^{0}}$

• Allender, E. (1996). "Una nota sobre límites inferiores de circuitos uniformes para la jerarquía de conteo". Actas de la 2.ª Conferencia Internacional de Informática y Combinatoria (COCOON) . Springer Lecture Notes in Computer Science . Vol. 1090. Págs. 127–135.
• Clote, Peter; Kranakis, Evangelos (2002). Funciones booleanas y modelos computacionales . Textos en informática teórica. Serie EATCS. ​​Berlín: Springer-Verlag . ISBN. 3-540-59436-1.Zbl 1016.94046  .
• Vollmer, Heribert (1999). Introducción a la complejidad de circuitos. Un enfoque uniforme . Textos en informática teórica. Berlín: Springer-Verlag . ISBN. 3-540-64310-9.Zbl 0931.68055  .
• Burtschick, Hans-Jörg; Vollmer, Heribert (1998). "Cuantificadores de Lindström y definibilidad del lenguaje hoja". Revista Internacional de Fundamentos de la Ciencia de la Computación . 9 (3): 277–294. doi :10.1142/S0129054198000180. ECCC  TR96-005.

• Zoológico de la complejidad : TC0