Complejidad espacial

Memoria de computadora necesaria para un algoritmo

La complejidad espacial de un algoritmo o una estructura de datos es la cantidad de espacio de memoria necesaria 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] Esto incluye el espacio de memoria utilizado por sus entradas, llamado espacio de entrada , y cualquier otra memoria (auxiliar) que use durante la ejecución, que se llama espacio auxiliar .

De manera 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. ${\displaystyle O(n),}$ ${\displaystyle O(n\log n),}$ ${\displaystyle O(n^{\alpha }),}$ ${\displaystyle O(2^{n}),}$

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 determinismo ( respectivamente, no deterministas) Máquinas de Turing que utilizan el espacio. Las clases de complejidad PSPACE y NPSPACE permiten ser cualquier polinomio, de forma análoga a P y NP . Eso es, ${\displaystyle O(f(n))}$ ${\displaystyle f}$

$${\displaystyle {\mathsf {PSPACE}}=\bigcup _{c\in \mathbb {Z} ^{+}}{\mathsf {DSPACE}}(n^{c})}$$

$${\displaystyle {\mathsf {NPSPACE}}=\bigcup _{c\in \mathbb {Z} ^{+}}{\mathsf {NSPACE}}(n^{c})}$$

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 espacio. ${\displaystyle f(n),}$ ${\displaystyle f(n)}$ ${\displaystyle f(n)}$

Se mantienen las siguientes contenciones entre clases de complejidad. ^[2]

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

Además, el teorema de Savitch da la contención inversa de que si ${\displaystyle f\in \Omega (\log(n)),}$

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

Como corolario directo, este resultado es sorprendente porque sugiere que el no determinismo puede reducir el espacio necesario para resolver un problema sólo en una pequeña cantidad. Por el contrario, 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. ${\displaystyle {\mathsf {PSPACE}}={\mathsf {NPSPACE}}.}$

El teorema de Immerman-Szelepcsényi establece que, nuevamente, for 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]} ${\displaystyle f\in \Omega (\log(n)),}$ ${\displaystyle {\mathsf {NSPACE}}(f(n))}$

ESPACIO DE REGISTRO

L o LOGSPACE es el conjunto de problemas que puede resolver una máquina de Turing determinista utilizando solo espacio de memoria con respecto al tamaño de entrada. Incluso un único contador que pueda indexar toda la entrada de bits requiere espacio, por lo que los algoritmos LOGSPACE pueden mantener sólo un número constante de contadores u otras variables de complejidad de bits similar. ${\displaystyle O(\log n)}$ ${\displaystyle n}$ ${\displaystyle \log n}$

LOGSPACE y otros espacios de complejidad sublineal son útiles cuando se procesan datos grandes que no caben en la RAM de una computadora . Están relacionados con los algoritmos de transmisión , pero solo restringen la cantidad de memoria que se puede usar, 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 desrandomización , donde los investigadores consideran el problema abierto de si L = RL . ^{[5] [6]}

La clase de complejidad espacial no determinista correspondiente es NL .

Complejidad del espacio auxiliar

El términoEl espacio auxiliar se refiere al espacio distinto al consumido por la entrada. La complejidad del espacio auxiliar podría definirse formalmente en términos de unamáquina de Turingcon unacinta de entradaen la que no se puede escribir, sólo leer, y una cinta de trabajo convencional en la que se puede escribir. Luego, la complejidad del espacio auxiliar se define (y analiza) a través de la cinta de trabajo. Por ejemplo, considere labúsqueda en profundidadde unárbol binario equilibradoconnodos: su complejidad espacial auxiliar es ${\displaystyle n}$ ${\displaystyle \Theta (\log n).}$

Ver también

• Análisis de algoritmos  – Estudio de los recursos utilizados por un algoritmo
• Teoría de la complejidad computacional  : dificultad inherente a los problemas computacionales
• Recurso computacional  : algo que una computadora necesita para resolver un problema, como pasos de procesamiento o memoria.

Referencias

1. Kuo, camino; Zuo, Ming J. (2003), Modelado de confiabilidad óptima: principios y aplicaciones, John Wiley & Sons, p. 62, ISBN 9780471275459
2. Arora, Sanjeev ; Barak, Boaz (2007), Complejidad computacional: un enfoque moderno (PDF) (borrador de edición), p. 76, ISBN 9780511804090
3. Immerman, Neil (1988), "El espacio no determinista está cerrado bajo complementación" (PDF) , SIAM Journal on Computing , 17 (5): 935–938, doi :10.1137/0217058, MR  0961049
4. Szelepcsényi, Róbert (1987), "El método de forzado para autómatas no deterministas", Boletín de la EATCS , 33 : 96-100
5. Nisan, Noam (1992), "RL ⊆ SC", Actas del 24º Simposio ACM sobre teoría de la informática (STOC '92) , Victoria, Columbia Británica, Canadá, págs. 619–623, doi :10.1145/129712.129772, S2CID  11651375{{citation}}: CS1 maint: location missing publisher (link).
6. Reingold, Omer ; Trevisan, Luca ; Vadhan, Salil (2006), "Paseos pseudoaleatorios sobre dígrafos regulares y el problema RL versus L" (PDF) , STOC'06: Actas del 38º Simposio anual de ACM sobre teoría de la computación , Nueva York: ACM, págs. 466, doi : 10.1145/1132516.1132583, SEÑOR  2277171, S2CID  17360260