Teorema de la brecha

Existen brechas computables arbitrariamente grandes en la jerarquía de clases de complejidad

Véase también Teorema de brecha (desambiguación) para otros teoremas de brecha en matemáticas .

En la teoría de la complejidad computacional , el teorema de la brecha, también conocido como el 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 demostrado independientemente 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 (de 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 de contorno 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 forma más sencilla:

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 puede ser muy grande ${\displaystyle T(n)}$ (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 del tiempo o el Teorema de la jerarquía del espacio . ^[6]

Véase también

• Teorema de aceleración de Blum

Referencias

1. Fortnow, Lance; Homer, Steve (junio de 2003). "Una breve historia de la complejidad computacional" (PDF) . Boletín de la Asociación Europea de Ciencias Informáticas Teóricas (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 clase) . Universidad de Novosibirsk.
3. Borodin, Allan (1969). "Clases de complejidad de funciones recursivas y la existencia de brechas de complejidad". En Fischer, Patrick C.; Ginsburg, Seymour; Harrison, Michael A. (eds.). Actas del 1.er Simposio Anual de la ACM sobre Teoría de la Computación, 5-7 de mayo de 1969, Marina del Rey, CA, EE. UU . . Association for Computing Machinery. 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. ; Loui, Michael C.; Regan, Kenneth W. (2014). "Capítulo 7: Teoría de la complejidad". En Gonzalez, Teofilo ; Diaz-Herrera, Jorge; Tucker, Allen (eds.). Computing Handbook, tercera edición: Ciencias de la computación e ingeniería de software. CRC Press. págs. 7-9. ISBN 9781439898529Afortunadamente , el fenómeno de la brecha no puede ocurrir durante períodos de tiempo que a nadie le interesarían ..
6. Zimand, Marius (2004). Complejidad computacional: una perspectiva cuantitativa. North-Holland Mathematics Studies. Vol. 196. Elsevier. pág. 42. ISBN 9780080476667..