En la teoría de la complejidad computacional de la informática , la teoría de la complejidad estructural o simplemente complejidad estructural es el estudio de las clases de complejidad , en lugar de la complejidad computacional de problemas y algoritmos individuales. Implica la investigación tanto de las estructuras internas de varias clases de complejidad como de las relaciones entre diferentes clases de complejidad. [1]
La teoría surgió como resultado de intentos (aún fallidos) de resolver la primera y aún más importante cuestión de este tipo, el problema P = NP . La mayor parte de la investigación se basa en el supuesto de que P no es igual a NP y en una conjetura de mayor alcance de que la jerarquía temporal polinómica de las clases de complejidad es infinita. [1]
El teorema de compresión es un teorema importante sobre la complejidad de las funciones computables .
El teorema establece que no existe una clase de complejidad máxima , con límite 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 el espacio n log n que en el 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 afirmaciones importantes sobre la computación limitada en el tiempo en las máquinas de Turing . De manera informal, estos teoremas dicen que, dado más tiempo, una máquina de Turing puede resolver más problemas. Por ejemplo, hay problemas que se pueden resolver con n 2 tiempos, pero no con n tiempos.
El teorema de Valiant-Vazirani es un teorema de la teoría de la complejidad computacional . Leslie Valiant y Vijay Vazirani lo demostraron en su artículo titulado NP is as easy as detecting unique solutions publicado en 1986. [2] El teorema establece que si existe un algoritmo de tiempo polinomial para SAT no ambiguo , entonces NP = RP . La prueba 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 Σ 2 ∩ Π 2 .
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 ,
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 de polinomios en tiempo" (1991) y recibió el Premio Gödel en 1998. El teorema establece que toda la jerarquía de polinomios 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 expresa de manera 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 [ cita requerida ] . El resultado resolvió el segundo problema LBA .
Las principales direcciones de investigación en esta área incluyen: [1]
