Teorema de la brecha

Hay lagunas computables arbitrariamente grandes en la jerarquía de clases de complejidad

Véase también 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, afirma que existen lagunas 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 recurso limitado 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 demostrado 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 que se publicó el trabajo de Borodin.

Teorema de la brecha

La forma general del teorema es la siguiente.

Supongamos que Φ es una medida de complejidad abstracta (Blum) . Para cualquier función computable total g para la cual para cada x , existe una función computable total t tal que con respecto a Φ , las clases de complejidad con funciones límite t y son idénticas. ${\displaystyle g(x)\geq x}$ ${\displaystyle g\circ t}$

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, al espacio o a cualquier otra medida de complejidad razonable.

Para el caso especial de complejidad temporal, 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 . ${\displaystyle g:\,\omega \,\to \,\omega }$ ${\displaystyle g(x)\geq x}$ ${\displaystyle T(n)}$ ${\displaystyle {\mathsf {DTIME}}(g(T(n)))={\mathsf {DTIME}}(T(n))}$

Debido a que el límite ⁠ ⁠ ${\displaystyle T(n)}$ puede ser muy grande (y a 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

• Teorema de aceleración de Blum

Referencias

1. Por ahora, Lance; Homero, Steve (junio de 2003). "Una breve historia de la complejidad computacional" (PDF) . Boletín de la Asociación Europea de Informática Teórica (80): 95–133. Archivado desde el original (PDF) el 29 de diciembre de 2005.
2. Trakhtenbrot, Boris A. (1967). La complejidad de los algoritmos y los cálculos (apuntes de la conferencia) . Universidad de Novosibirsk.
3. Borodin, Allan (1969). "Clases de complejidad de funciones recursivas y existencia de brechas de complejidad". En Fischer, Patrick C.; Ginsburg, Seymour; Harrison, Michael A. (eds.). Actas del primer simposio anual de ACM sobre teoría de la computación, 5 al 7 de mayo de 1969, Marina del Rey, CA, EE. UU . Asociación para Maquinaria de Computación. págs. 67–78.
4. 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 . hdl : 1813/5899 .
5. Allender, Eric W .; Luis, Michael C.; Reagan, Kenneth W. (2014). "Capítulo 7: Teoría de la complejidad". En González, Teófilo ; Díaz-Herrera, Jorge; Tucker, Allen (eds.). Manual de informática, tercera edición: informática e ingeniería de software. Prensa CRC. pag. 7-9. ISBN 9781439898529. Afortunadamente, el fenómeno de la brecha no puede ocurrir durante límites de tiempo en los que alguien estaría interesado..
6. Zimand, Marius (2004). Complejidad computacional: una perspectiva cuantitativa. Estudios de Matemáticas de Holanda Septentrional. vol. 196. Elsevier. pag. 42.ISBN​ 9780080476667..