ESPACIO

---

En la teoría de la complejidad computacional , DSPACE o ESPACIO es el recurso computacional que describe el recurso de espacio de memoria para una máquina de Turing determinista . Representa la cantidad total de espacio de memoria que una computadora física "normal" necesitaría para resolver un problema computacional dado con un algoritmo dado .

La medida DSPACE se usa para definir clases de complejidad , conjuntos de todos los problemas de decisión que se pueden resolver usando una cierta cantidad de espacio de memoria. Para cada función f ( n ), existe una clase de complejidad ESPACIO ( f ( n )), el conjunto de problemas de decisión que puede resolver una máquina de Turing determinista utilizando el espacio O ( f ( n )). No hay restricciones en la cantidad de tiempo de cálculo que se puede usar, aunque puede haber restricciones en algunas otras medidas de complejidad (comoalternancia ).

Prueba: Supongamos que existe un lenguaje no regular L ∈ DSPACE( s ( n )), para s ( n ) = o (log log n ). Sea M una máquina de Turing que decide L en el espacio s ( n ). Por nuestra suposición L ∉ DSPACE( O (1)); por lo tanto, para cualquier , existe una entrada de M que requiere más espacio que k .${\displaystyle k\en \mathbb {N} }$

Sea x una entrada de menor tamaño, denotada por n, que requiere más espacio que k , y sea el conjunto de todas las configuraciones de M en la entrada x . Como M ∈ DSPACE( s ( n )), entonces , donde c es una constante que depende de M .${\displaystyle {\mathcal {C}}}$${\displaystyle |{\mathcal {C}}|\leq 2^{c.s(n)}=o(\log n)}$

Sea S el conjunto de todas las posibles secuencias de cruce de M sobre x . Tenga en cuenta que la longitud de una secuencia de cruce de M en x es como máximo : si es más larga que eso, entonces se repetirá alguna configuración y M entrará en un ciclo infinito. También hay como máximo posibilidades para cada elemento de una secuencia de cruce, por lo que el número de secuencias de cruce diferentes de M en x es${\displaystyle |{\mathcal {C}}|}$${\displaystyle |{\mathcal {C}}|}$

De acuerdo con el principio del casillero , existen índices i < j tales que , donde y son las secuencias de cruce en el límite i y j , respectivamente.${\displaystyle {\mathcal {C}}_{i}(x)={\mathcal {C}}_{j}(x)}$${\displaystyle {\mathcal {C}}_{i}(x)}$${\displaystyle {\mathcal {C}}_{j}(x)}$

---