Teorema de la brecha

Véase también Teorema de la 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 ]}

En esencia, 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 ampliado 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 publicara el trabajo de Borodin.

Como ejemplo introductorio, supongamos que estamos considerando la complejidad temporal de un modelo específico de máquina de Turing . El conjunto${\displaystyle \operatorname {TIEMPO} (n^{2})}$es el conjunto de funciones computables totales, de modo que existe alguna implementación de la función que la calcula en tiempo${\displaystyle \leq n^{2}}$dado un tamaño de entrada de${\displaystyle n}$.

En general, cualquier función computable total${\displaystyle t}$define algunos${\displaystyle \operatorname {TIEMPO} (t(n))}$clase de complejidad temporal, y esperamos que si${\displaystyle t'(n)}$es mucho más grande que${\displaystyle t(n)}$, para todos${\displaystyle n}$, entonces${\displaystyle \operatorname {TIEMPO} (t'(n))}$debería ser más grande que${\displaystyle \operatorname {TIEMPO} (t(n))}$El teorema de la brecha establece que esto no es necesariamente así. De hecho, para cualquier total computable${\displaystyle g}$de tal manera que${\displaystyle g(n)>n}$a pesar de${\displaystyle n}$, existe alguna función computable total${\displaystyle t}$, de tal manera que${\displaystyle \operatorname {TIEMPO} (t(n))=\operatorname {TIEMPO} (g(t(n)))}$Intuitivamente, aumentar el tiempo de cómputo podría no permitirnos calcular más funciones.

De forma más general, supongamos que Φ es una medida de complejidad abstracta (Blum) , entonces para cualquier función computable total g para la cual${\displaystyle g(x)\geq x}$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${\displaystyle g\circ t}$son idénticos.

• Teorema de aceleración de Blum