Teoría de la complejidad estructural

El teorema de compresión es un teorema importante sobre la complejidad de las funciones computables .

El teorema establece que no existe ninguna clase de complejidad máxima , con frontera computable, que contenga todas las funciones computables.

Los teoremas de jerarquía espacial son resultados de separación que muestran que tanto las máquinas deterministas como las no deterministas pueden resolver más problemas en un espacio (asintóticamente) mayor, sujeto a ciertas condiciones. Por ejemplo, una máquina de Turing determinista puede resolver más problemas de decisión en un espacio n log n que en un espacio n . Los teoremas análogos, algo más débiles, para el tiempo son los teoremas de jerarquía temporal .

Los teoremas de jerarquía temporal son enunciados importantes sobre la computación con límite de tiempo en máquinas de Turing . De manera informal, estos teoremas afirman que, con más tiempo, una máquina de Turing puede resolver más problemas. Por ejemplo, hay problemas que se pueden resolver con n² tiempo ^, pero no con n tiempo.

El teorema de Valiant-Vazirani es un teorema de la teoría de la complejidad computacional . Fue demostrado por Leslie Valiant y Vijay Vazirani en su artículo titulado NP es tan fácil como detectar soluciones únicas, publicado en 1986. ^{[ 2 ]} El teorema establece que si existe un algoritmo de tiempo polinomial para Unambiguous-SAT , entonces NP = RP . La demostración se basa en el lema de aislamiento de Mulmuley-Vazirani , que posteriormente se utilizó para varias aplicaciones importantes en la informática teórica .

El teorema de Sipser-Lautemann o teorema de Sipser-Gács-Lautemann establece que el tiempo polinomial probabilístico de error acotado (BPP) está contenido en la jerarquía del tiempo polinomial , y más específicamente Σ ₂ ∩ Π ₂ .

El teorema de Savitch, demostrado por Walter Savitch en 1970, establece una relación entre la complejidad espacial determinista y no determinista . Afirma que para cualquier función${\displaystyle f\in \Omega (\log(n))}$,

${\displaystyle {\mathsf {NSPACE}}\left(f\left(n\right)\right)\subseteq {\mathsf {DSPACE}}\left(\left(f\left(n\right)\right)^{2}\right).}$

El teorema de Toda es un resultado que fue demostrado por Seinosuke Toda en su artículo "PP es tan difícil como la jerarquía polinomial-temporal" (1991) y que recibió el Premio Gödel en 1998. El teorema afirma que toda la jerarquía polinomial PH está contenida en P ^PP ; esto implica una afirmación estrechamente relacionada, que PH está contenida en P ^#P .

El teorema de Immerman-Szelepcsényi fue demostrado independientemente por Neil Immerman y Róbert Szelepcsényi en 1987, por lo que compartieron el Premio Gödel de 1995. En su forma general, el teorema establece que NSPACE ( s ( n )) = co-NSPACE( s ( n )) para cualquier función s ( n ) ≥ log n . El resultado se puede expresar de forma equivalente como NL = co-NL; aunque este es el caso especial cuando s ( n ) = log n , implica el teorema general mediante un argumento de relleno estándar . El resultado resolvió el segundo problema LBA .