TC0

Clase de complejidad utilizada en la complejidad del circuito.

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.

Relaciones de clases de complejidad

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

${\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}}}$

Bases para un TC uniforme0

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,n-m)}$ ${\displaystyle n\wedge m}$ ${\displaystyle n}$ ${\displaystyle m}$ ${\displaystyle f(x_{1},\ldots ,x_{n})}$ ${\displaystyle (y{\text{-th bit of }}f(x_{1},\ldots ,x_{n}))}$ ${\displaystyle {\mbox{TC}}^{0}}$

Referencias

1. Hesse, William; Allender, Eric; Mix Barrington, David (2002). "Circuitos de umbral de profundidad constante uniformes para división y multiplicación iterada". Revista de Ciencias de la Computación y de Sistemas . 65 (4): 695–716. doi : 10.1016/S0022-0000(02)00025-9 .
2. Volkov, Sergey. (2016). "Bases finitas con respecto a la superposición en clases de funciones recursivas elementales, tesis doctoral". arXiv : 1611.04843 [cs.CC].

• Allender, E. (1996). "Una nota sobre los 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.

Enlaces externos

• Zoológico de la complejidad : TC0