Clase de complejidad utilizada en la complejidad del circuito.
TC 0 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 0 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 0 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 0 con otras clases de circuitos, incluidos AC 0 y NC 1 ; Vollmer 1999 p. 126 afirma:
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).
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 .
Referencias
- ^ 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 .
- ^ 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