La complejidad espacial de un algoritmo o un programa de computadora es la cantidad de espacio de memoria requerido para resolver una instancia del problema computacional en función de las características de la entrada. Es la memoria que requiere un algoritmo hasta que se ejecuta por completo. [1]
Similar a la complejidad del tiempo , la complejidad del espacio a menudo se expresa asintóticamente en notación O grande , como etc., donde n es una característica de la entrada que influye en la complejidad del espacio.
Clases de complejidad espacial
De manera análoga a las clases de complejidad temporal DTIME (f (n)) y NTIME (f (n)) , las clases de complejidad DSPACE (f (n)) y NSPACE (f (n)) son los conjuntos de lenguajes que se pueden decidir mediante deterministas ( respectivamente, no deterministas) máquinas de Turing que utilizanespacio. Las clases de complejidad PSPACE y NPSPACE permitenser cualquier polinomio, análogamente a P y NP . Es decir,
y
Relaciones entre clases
El teorema de la jerarquía espacial establece que, para todas las funciones construibles en el espacio , existe un problema que puede ser resuelto por una máquina con espacio de memoria, pero no puede ser resuelto por una máquina con asintóticamente menos de espacio.
Se mantienen las siguientes contenciones entre clases de complejidad. [2]
Además, el teorema de Savitch da la contención inversa de que si,
Como corolario directo, . Este resultado es sorprendente porque sugiere que el no determinismo puede reducir el espacio necesario para resolver un problema solo en una pequeña cantidad. En contraste, la hipótesis del tiempo exponencial conjetura que para la complejidad del tiempo, puede haber una brecha exponencial entre la complejidad determinista y no determinista.
El teorema de Immerman-Szelepcsényi establece que, nuevamente para, está cerrado bajo complementación. Esto muestra otra diferencia cualitativa entre las clases de complejidad temporal y espacial, ya que no se cree que las clases de complejidad temporal no deterministas estén cerradas bajo complementación; por ejemplo, se conjetura que NP ≠ co-NP . [3] [4]
ESPACIO DE REGISTRO
L o LOGSPACE es el conjunto de problemas que puede resolver una máquina de Turing determinista utilizando soloespacio de memoria con respecto al tamaño de entrada. Incluso un solo contador que puede indexar todo-La entrada de bits requiere espacio, por lo que los algoritmos LOGSPACE pueden mantener solo un número constante de contadores u otras variables de complejidad de bits similar.
LOGSPACE y otra complejidad de espacio sub-lineal es útil cuando se procesan datos grandes que no caben en la RAM de una computadora . Están relacionados con los algoritmos de transmisión por secuencias , pero solo restringen la cantidad de memoria que se puede utilizar, mientras que los algoritmos de transmisión tienen restricciones adicionales sobre cómo se introduce la entrada en el algoritmo. Esta clase también se utiliza en el campo de la pseudoaleatorización y la desaleatorización , donde los investigadores consideran el problema abierto de si L = RL . [5] [6]
La clase de complejidad espacial no determinista correspondiente es NL .
Referencias
- ^ Kuo, Camino; Zuo, Ming J. (2003), Modelado de confiabilidad óptima: Principios y aplicaciones , John Wiley & Sons, p. 62, ISBN 9780471275459
- ^ Arora, Sanjeev ; Barak, Boaz (2007), Computational Complexity: A Modern Approach (PDF) (borrador ed.), P. 76, ISBN 9780511804090
- ^ Immerman, Neil (1988), "El espacio no determinista se cierra bajo complementación" (PDF) , SIAM Journal on Computing , 17 (5): 935–938, doi : 10.1137 / 0217058 , MR 0961049
- ^ Szelepcsényi, Róbert (1987), "El método de forzar para autómatas no deterministas", Boletín de la EATCS , 33 : 96–100
- ^ Nisan, Noam (1992), "RL ⊆ SC", Actas del 24º Simposio ACM sobre Teoría de la Computación (STOC '92) , Victoria, Columbia Británica, Canadá, págs. 619–623, doi : 10.1145 / 129712.129772.
- ^ Reingold, Omer ; Trevisan, Luca ; Vadhan, Salil (2006), "Pseudoaleatorio camina sobre dígrafos regulares y el problema RL vs. L" (PDF) , STOC'06: Actas del 38º Simposio Anual de ACM sobre Teoría de la Computación , Nueva York: ACM, págs. 457– 466, doi : 10.1145 / 1,132,516.1132583 , MR 2277171