- Consulte también el teorema de la brecha (desambiguación) para conocer otros teoremas de la brecha en matemáticas .
En la teoría de la complejidad computacional , el teorema de la brecha, también conocido como teorema de la brecha de Borodin-Trakhtenbrot, es un teorema importante sobre la complejidad de las funciones computables . [1]
Básicamente, establece que existen brechas computables arbitrariamente grandes en la jerarquía de clases de complejidad . Para cualquier función computable que represente un aumento en los recursos computacionales , se puede encontrar un límite de recursos tal que el conjunto de funciones computables dentro del límite de recursos expandido sea el mismo que el conjunto computable dentro del límite original.
El teorema fue probado de forma independiente por Boris Trakhtenbrot [2] y Allan Borodin . [3] [4] Aunque la derivación de Trakhtenbrot precedió a la de Borodin por varios años, no fue conocida ni reconocida en Occidente hasta después de la publicación del trabajo de Borodin.
Teorema de la brecha
La forma general del teorema es la siguiente.
- Suponga que Φ es una medida de complejidad abstracta (Blum) . Para cualquier función computable total g para la cual para cada x , hay una función calculable total t tal que con respecto a Φ , las clases de complejidad con funciones de frontera t y Son identicos.
El teorema se puede demostrar utilizando los axiomas de Blum sin ninguna referencia a un modelo computacional concreto , por lo que se aplica al tiempo, espacio o cualquier otra medida de complejidad razonable.
Para el caso especial de la complejidad del tiempo, esto se puede expresar de manera más simple como:
- para cualquier función computable total tal que para todo x , existe un límite de tiempo tal que .
Porque el límite puede ser muy grande (ya menudo no será construible ) el Teorema de la brecha no implica nada interesante para clases de complejidad como P o NP, [5] y no contradice el teorema de la jerarquía temporal o el teorema de la jerarquía espacial . [6]
Ver también
Referencias
- ^ Fortnow, Lance; Homer, Steve (junio de 2003). "Una breve historia de la complejidad computacional" (PDF) . Boletín de la Asociación Europea de Ciencias de la Computación Teórica (80): 95-133. Archivado desde el original (PDF) el 29 de diciembre de 2005.
- ^ Trakhtenbrot, Boris A. (1967). La complejidad de los algoritmos y cálculos (notas de clase) . Universidad de Novosibirsk.
- ^ Allan Borodin (1969). "Clases de complejidad de funciones recursivas y la existencia de brechas de complejidad". Proc. del 1er Simposio Anual de ACM sobre Teoría de la Computación : 67–78.
- ^ Borodin, Allan (enero de 1972). "Complejidad computacional y existencia de brechas de complejidad". Revista de la ACM . 19 (1): 158-174. doi : 10.1145 / 321679.321691 .
- ^ Allender, Eric W .; Loui, Michael C .; Regan, Kenneth W. (2014), "Capítulo 7: Teoría de la complejidad", en González, Teófilo ; Díaz-Herrera, Jorge; Tucker, Allen (eds.), Computing Handbook, Tercera Edición: Ciencias de la Computación e Ingeniería de Software , CRC Press, p. 7-9, ISBN 9781439898529,
Afortunadamente, el fenómeno de la brecha no puede ocurrir durante los límites de tiempo t en los que alguien alguna vez estaría interesado
. - ^ Zimand, Marius (2004), Computational Complexity: A Quantitative Perspective , North-Holland Mathematics Studies, 196 , Elsevier, p. 42, ISBN 9780080476667.