Complejidad espacial

La complejidad espacial de un algoritmo o una estructura de datos 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 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 denomina espacio auxiliar .

De forma similar a la complejidad temporal , la complejidad espacial se expresa a menudo asintóticamente en notación O grande , como por ejemplo:${\displaystyle O(n),}$${\displaystyle O(n\log n),}$${\displaystyle O(n^{\alpha }),}$${\displaystyle O(2^{n}),}$etc., donde n es una característica de la entrada que influye en la complejidad espacial.

De forma 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 pueden ser decididos por máquinas de Turing deterministas (respectivamente, no deterministas) que utilizan${\displaystyle O(f(n))}$espacio. Las clases de complejidad PSPACE y NPSPACE permiten${\displaystyle f}$ser cualquier polinomio, análogamente a P y NP . Es decir, $${\displaystyle {\mathsf {PSPACE}}=\bigcup _{c\in \mathbb {Z} ^{+}}{\mathsf {DSPACE}}(n^{c})}$$ y $${\displaystyle {\mathsf {NPSPACE}}=\bigcup _{c\in \mathbb {Z} ^{+}}{\mathsf {NSPACE}}(n^{c})}$$

El teorema de jerarquía espacial establece que, para todas las funciones construibles en el espacio,${\displaystyle f(n),}$existe un problema que puede ser resuelto por una máquina con${\displaystyle f(n)}$espacio de memoria, pero no puede ser resuelto por una máquina con asintóticamente menos de${\displaystyle f(n)}$espacio.

Se cumplen las siguientes relaciones de contención 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 que si${\displaystyle f\in \Omega (\log(n)),}$$${\displaystyle {\mathsf {NSPACE}}(f(n))\subseteq {\mathsf {DSPACE}}\left((f(n))^{2}\right).}$$

Como corolario directo,${\displaystyle {\mathsf {PSPACE}}={\mathsf {NPSPACE}}.}$Este resultado es sorprendente porque sugiere que el no determinismo solo puede reducir el espacio necesario para resolver un problema en una pequeña cantidad. En contraste, la hipótesis del tiempo exponencial postula que, para la complejidad temporal, puede existir una brecha exponencial entre la complejidad determinista y la no determinista.

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

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

LOGSPACE y otras complejidades espaciales sublineales son útiles para procesar grandes cantidades de datos que no caben en la RAM de un ordenador . Están relacionadas con los algoritmos de procesamiento en tiempo real (streaming) , pero solo restringen la cantidad de memoria que se puede usar, mientras que estos últimos imponen restricciones adicionales sobre cómo se introduce la entrada al algoritmo. Esta clase también se utiliza en el campo de la pseudoaleatoriedad y la desaleatorización , donde los investigadores analizan el problema abierto de si L = RL . ^{[ 5 ] [ 6 ]}

La clase de complejidad espacial no determinista correspondiente es NL .

El términoEl espacio auxiliar se refiere al espacio distinto del 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, solo leer, y una cinta de trabajo convencional en la que sí se puede escribir. La complejidad del espacio auxiliar se define (y analiza) a través de la cinta de trabajo. Por ejemplo, considérese labúsqueda en profundidadde unárbol binario equilibradocon${\displaystyle n}$nodos: su complejidad espacial auxiliar es${\displaystyle \Theta (\log 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 : un aspecto de la teoría de la complejidad computacional. 
• Complejidad temporal : estimación del tiempo necesario para ejecutar un algoritmo.