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 requerida para resolver una instancia del problema computacional en función de las características de la entrada. Es la memoria requerida por 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 utilice durante la ejecución, que se llama espacio auxiliar .

De manera similar a la complejidad temporal , la complejidad espacial 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 espacial. ${\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 son decidibles por máquinas de Turing deterministas (respectivamente, no deterministas) que usan el espacio. Las clases de complejidad PSPACE y NPSPACE permiten ser cualquier polinomio, de manera análoga a P y NP . Es decir, y ${\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 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 espacio asintóticamente menor . ${\displaystyle f(n),}$ ${\displaystyle f(n)}$ ${\displaystyle f(n)}$

Se cumplen 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 proporciona la contención inversa, es decir, 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 solo en una pequeña cantidad. En contraste, la hipótesis del tiempo exponencial conjetura que, para la complejidad temporal, puede haber una brecha exponencial entre la complejidad determinista y la no determinista. ${\displaystyle {\mathsf {PSPACE}}={\mathsf {NPSPACE}}.}$

El teorema de Immerman–Szelepcsényi establece que, nuevamente, para es 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 sean 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 solo contador que pueda indexar toda la entrada de 1000 bits requiere espacio, por lo que los algoritmos LOGSPACE solo pueden mantener una cantidad constante de contadores u otras variables de complejidad de bits similar. ${\displaystyle O(\log n)}$ ${\displaystyle n}$ ${\displaystyle \log n}$

LOGSPACE y otras complejidades espaciales sublineales son útiles cuando se procesan datos grandes que no caben en la RAM de una computadora . Están relacionados con los algoritmos de Streaming , pero solo restringen la cantidad de memoria que se puede usar, mientras que los algoritmos de streaming tienen restricciones adicionales sobre cómo se alimenta la entrada al algoritmo. Esta clase también se usa en el campo de la pseudoaleatoriedad y la desaleatoriedad , 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 del que consume 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, solo leer, y una cinta de trabajo convencional en la que se puede escribir. 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 balanceadoconnodos: su complejidad del espacio auxiliar es ${\displaystyle n}$ ${\displaystyle \Theta (\log n).}$

Véase también

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

Referencias

1. Kuo, Way; Zuo, Ming J. (2003), Modelado de confiabilidad óptima: principios y aplicaciones, John Wiley & Sons, pág. 62, ISBN 9780471275459
2. Arora, Sanjeev ; Barak, Boaz (2007), Computational Complexity: A Modern Approach (PDF) (edición preliminar), pág. 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 computación (STOC '92) , Victoria, Columbia Británica, Canadá, págs. 619-623, doi :10.1145/129712.129772, ISBN 0-89791-511-9, Número de identificación del sujeto  11651375{{citation}}: Mantenimiento de CS1: falta la ubicación del editor ( enlace ).
6. Reingold, Omer ; Trevisan, Luca ; Vadhan, Salil (2006), "Caminatas pseudoaleatorias en dígrafos regulares y el problema RL vs. L" (PDF) , STOC'06: Actas del 38.º Simposio Anual de la ACM sobre Teoría de la Computación , Nueva York: ACM, pp. 457–466, doi :10.1145/1132516.1132583, ISBN 1-59593-134-1, MR  2277171, S2CID  17360260