Referencias: Sipser cap. 8, Arora Barak cap. 4
Sea s : ℕ ↦ N y L ⊆ {0, 1} * .
Decimos que L ∈ SPACE(s(n)) si existe una MT M y una constante c tal que M decide L y además, para todo input de longitud n, M visita cómo máximo cs(n) casillas en sus cintas (excluyendo la cinta de input) durante la computación.
Observación: como M decide L, M se detiene después de un número finito de pasos.
Sea s : ℕ ↦ N y L ⊆ {0, 1} * .
Decimos que L ∈ NSPACE(s(n)) si existe una MTND M cuyas ejecuciones nondeterministas cumplen con el mismo límite de espacio.
Observación: los caminos que no llegan a qaccept pueden ser infinitos.
Trabajamos con cotas espaciales s : ℕ ↦ ℕ que son constructibles en espacio, ie:
Asumimos lo siguiente:
Se puede hacer una simulación universal de una máquina con k cintas de trabajo por una máquina con una sola cinta de trabajo, con sólo un gasto de espacio más grande por una constante multiplicativa.
Entonces, podemos asumir sin perdida de generalidad que hablamos de complejidad espacial con máquinas con solo 1 cinta de trabajo.
Si f, g son funciones constructibles en espacio tales que f(n) ∈ o(g(n)), entonces
SPACE(f(n)) ⊂ ≠ SPACE(g(n))
Demo: a lo time hierarchy theorem.
Stearns, Hartmanis y Lewis, Hierarchies of memory limited computations 1965
Sipser Sección 9.1: Space hierarchy theorem
En cada paso, una MT determinista puede descubrir cómo máximo un número constante de casillas nuevas, entonces:
Una configuración de una MT M es el contenido de todas las casillas no blancas de las cintas, las posiciones de sus cabezales y su estado.
Si una MT corre en espacio O(s(n)), entonces una configuración ocupa un espacio O(s(n)).
Sea M una MT determinista o nondeterminista, x ∈ {0, 1} * .
El grafo de configuraciones de M, llamado GM, x, es un grafo dirigido cuyos nodos corresponden a todas las configuraciones posibles de M cuando el input es x.
GM, x tiene un eje de la configuración C a la configuración C′ si C′ es alcanzable a partir de C en un paso según la(s) función(es) de transición de M.
Podemos siempre modificar M para que borre su cinta y ponga sus cabezales en posición inicial cuando acepta el input → hay sólo una configuración final Caccept.
Sea M una MT(ND) usando espacio s(n). El número de configuraciones CM(n) de M con input n es acotado por:
CM(n) ≤ |QM| ⋅ n ⋅ s(n) ⋅ |ΣM|s(n)
con |QM| los estados de M, |ΣM| su alfabeto.
En particular si s(n) ≥ log(n) tenemos CM(n) = 2O(s(n)).
Para toda s : ℕ ↦ ℕ constructible en espacio:
TIME(s(n)) ⊆ SPACE(s(n)) ⊆ NSPACE(s(n)) ⊆ TIME(2O(s(n)))Demo SPACE(s(n)) ⊆ TIME(2O(s(n))):
Sea L ∈ SPACE(s(n)) y M una MT corriendo en espacio O(s(n)) decidiendo L. Consideramos el cálculo de M(x) con x input de longitud n.
Hay como máximo CM(n) = 2O(s(n)) configuraciones de M con input x, pero si M(x) repite una configuración entonces buclearía y nunca se detendría.
Entonces M con input x se detiene en CM(n) = 2O(s(n)) pasos.
Demo NSPACE(s(n)) ⊆ TIME(2O(s(n))) por "reachability method". Sea M que decide L ∈ NPSPACE(s(n)):
PSPACE = ⋃c > 0 SPACE(nc)
NPSPACE = ⋃c > 0 NSPACE(nc)
L = SPACE(log(n))
NL = NSPACE(log(n))
3SAT ∈ PSPACE
Dado input ⌊φ⌋, buclear enumerando todas las asignaciones de variables de φ y chequear el valor de φ(zi).
Espacio usado para las asignacíones: polinomial (reutilizar para cada asignación nueva).
Espacio usado para el chequeo: polinomial (cuota espacial de un algoritmo determinístico en tiempo polinomial).
Sea L ∈ NP.
Dado input x, buclear sobre todos los certificados posibles de x con respeto a L. Se puede reutilizar el espacio (polinomial) usado para alojar un certificado, para el certificado siguiente.
El chequeo de cada certificado se hace en tiempo determinístico polinomial en función de |x|, entonces en espacio polinomial en función de |x|.
PATH = {⌊G, s, t⌋ ∣ G es un grafo dirigido con camino de s a t}
Sea n la cantidad de nodos en el grafo.
La idea del algoritmo es explorar todos los caminos de longitud < n posibles a partir de s, pasar al estado qaccept si encontramos t.
Solo necesitamos guardar dos cosas en memoria:
Un lenguaje L es PSPACE hard si para todo L′ ∈ PSPACE, L′ ≤ pL.
Si además L ∈ PSPACE, L es PSPACE completo.
Usamos las mismas reducciones que para NP, ie, f corriendo en tiempo polinomial.
Ya vimos ese truco con NP.
SPACESAT = {⌊M, w, 1n⌋ ∣ M MTD, acepta w en espacio n}
Una Quantified Boolean Formula es una formula proposicional con cuantificación (∀ y ∃) sobre sur variables booleanas.
Una QBF está en forma prenexa si tiene todos los cuantificadores primeros:
Q1x1Q2x2…Qnxn φ(x1, x2, …, xn)
Asumimos que todas las variables están cuantificadas.
Una QBF es verdadera o falsa (todos los xi son cuantificados).
Verdadera: ∀x∃y.(x ∧ y) ∨ (¬x ∧ ¬y)
Falsa: ∀x∀y.(x ∧ y) ∨ (¬x ∧ ¬y)
Se puede reescribir una QBF φ en una formula proposicional φ′ equisatisfacible, pero de tamaño exponencialmente más grande:
Una formula booleana es una QBF sin cuantificadores existenciales.
TQBF = {⌊φ⌋ ∣ formulas booleanas cuantificadas verdaderas }
TQBF es PSPACE completo
Stockmeyer y Meyer, Word problems requiring exponential time, 1973
Describimos el algoritmo A para TQBF:
Sea n el número de variables del input ψ, y m su tamaño.
Escribimos ψ[xi = b] para ψ con xi reemplazado por b ∈ {0, 1}.
Si n = 0 se puede evaluar ψ en tiempo (y espacio) O(m).
Si n > 0:
Sea sn, m el espacio usado para una llamada a A.
Una vez terminada una llamada recursiva a A, se puede reutilizar el espacio usado.
A usa O(m) espacio para escribir ψ[xi = b].
sn, m = sn − 1, m + O(m) = O(n ⋅ m)
A necesita un espacio polinomial y decide TQBF.
Para s : ℕ ↦ ℕ constructible en espacio:
NSPACE(s(n)) ⊆ SPACE(s(n)2)
L = SPACE(log(n))
NL = NSPACE(log(n))
¿Que se puede alojar en espacio log?
Ya vimos que PATH ∈ NL.
uPATH ∈ L (Reingold 2004)
{0k1k ∣ k ≥ 0} ∈ L:
Un transductor logspace es una máquina con 3 cintas:
Un transductor M computa una función (en espacio logarítmico) f : {0, 1} * ↦ {0, 1} * si para todo input x, M se detiene con f(x) escrito en la cinta de output.
¿Tamaño posible de f(x)?
Si para dos lenguajes B, C, existe una función f computable en espacio logarítmico tal que para todo x ∈ {0, 1} * , x ∈ B ssi f(x) ∈ C, entonces decimos que B es reducible en espacio logarímico a C (escrito B ≤ LC).
C ∈ NL es NL completo si para todo B ∈ NL, B ≤ LC.
Si B ≤ LC y C ∈ L entonces B ∈ L.
Si T es un transductor logspace que computa x ↦ f(x), entonces existe T′ que computa ⌊x, i⌋ ↦ f(x)i en espacio log.
Volviendo a la demostración de B ∈ L:
B ∈ NL si existe una MT M determinista con una cinta adicional en lectura unidireccional, y un polinomio p : ℕ ↦ ℕ tal que para todo x ∈ {0, 1} * :
x ∈ B ↔ ∃u ∈ {0, 1}p(|x|)s.t.M(x, u) = 1
Con:
Mostramos que B ∈ NLnd ⇔ B ∈ NLcert
∃ MTND N logspace ⇔ ∃ MTD M logspace con certificado
coPATH ∈ NL
Mostramos que hay un algoritmo A corriendo en espacio O(log(n)) tal que:
A(G, s, t, u) = 1 ssi t no es alcanzable desde s en G, con certificado u en lectura unidireccional.
Llamamos:
Para cualquier input, A ya sabe:
C0 = {s}
c0 = 1
v ∈ Ci puede ser chequeado facilmente: un certificado pathi(s, v) en lectura unidireccional es la secuencia de nodos v0, v1, …, vk del camino de s a v (k ≤ i).
Además de pathi(s, v) necesitamos dos tipos de certificados:
Con certificados de tipo 2 nos podemos enterar de los valores c1, …, cn, y al final con un certificado de tipo 1, convencernos que t ∉ Cn.
Certificado noPathi(s, v), asumiendo ci − 1 está conocido:
v1, pathi − 1(s, v1), …, vci − 1, pathi − 1(s, vci − 1)
con v1, …vci − 1 ∈ Ci − 1.
Se puede chequear que
en espacio O(log(n)) con certificado en lectura unidireccional.
Certificado sizei(k), asumiendo ci − 1 está conocido:
v1, (no)Pathi(s, v1), v2, (no)Pathi(s, v2), …, vn, (no)Pathi(s, vn)
dependiendo de si v ∈ Ci o no.
Se puede chequear que
en espacio log. con certificado en lectura unidireccional.
Un certificado de (G, s, t) ∉ PATH es:
size1(c1), size2(c2), …, sizen − 1(cn − 1), noPathn(s, t)
Cada certificado sizei(ci) puede ser chequeado en espacio log. y después de cada chequeo el verificador sólo necesita alojar ci.
Entonces todo el chequeo se hace en espacio log.
Si s : ℕ ↦ ℕ constructible en tiempo ( ≥ log(n)), entonces NSPACE(s(n)) = coNSPACE(s(n)).
Demo: Sea B ∈ coNSPACE(s(n)).
Entonces existe MTND M que usa espacio s(n) tal que x ∈ B ssi ninguna secuencia de elecciones de M con input x llega a qaccept.
Existe un transductor TB que computa x ↦ ⌊GM, x, Cstart, Caccept⌋ en espacio O(s(n)).
noPATH ∈ NL ie existe MTND N que decide noPATH en espacio log.
Componiendo TB y N de manera perezosa, obtenemos M′ que decide B en espacio O(s(n)), ie, B ∈ NSPACE(s(n)).