Resumen Unidad 2

consideramos clases de lenguajes
son definidas por la cantidad de tiempo o de espacio necesario para decidir un lenguaje
P: clases de los lenguajes fáciles
más recursos → inclusiones estrictas de clases de complejidad
reducciones entre lenguajes
lenguaje difícil (hard) o completo (complete) con respeto a una clase
clase NP definida con certificados o con nondeterminismo
3SAT (y varios otros lenguajes) es NP completo

Preguntas

¿implicaciones de P=NP?
¿implicaciones de P ≠ NP?

Contenido Unidad 3

cálculos acotados por espacio
clases PSPACE, NPSPACE
relación con P, NP, EXPTIME
problemas completos para clases espaciales
clases espaciales sublineales (L, NL)

Referencias: Sipser cap. 8, Arora Barak cap. 4

SPACE

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.

NSPACE

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 q_accept pueden ser infinitos.

Precaución

Trabajamos con cotas espaciales s : ℕ ↦ ℕ que son constructibles en espacio, ie:

s(n) ≥ log(n)
existe una MT que computa s(|x|) en espacio O(s(|x|)) dada x como input.

Simulación universal

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.

Space hierarchy theorem

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

TIME y SPACE

En cada paso, una MT determinista puede descubrir cómo máximo un número constante de casillas nuevas, entonces:

TIME(s(n)) ⊆ SPACE(s(n))

Configuraciónes

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)).

Grafo de configuraciones

Sea M una MT determinista o nondeterminista, x ∈ {0, 1}^*.

El grafo de configuraciones de M, llamado G_M, x, es un grafo dirigido cuyos nodos corresponden a todas las configuraciones posibles de M cuando el input es x.

G_M, 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 C_accept.

Sea M una MT(ND) usando espacio s(n). El número de configuraciones C_M(n) de M con input n es acotado por:

C_M(n) ≤ |Q_M| ⋅ n ⋅ s(n) ⋅ |Σ_M|^s(n)

con |Q_M| los estados de M, |Σ_M| su alfabeto.

En particular si s(n) ≥ log(n) tenemos C_M(n) = 2^O(s(n)).

Para toda s : ℕ ↦ ℕ constructible en espacio:

TIME(s(n)) ⊆ SPACE(s(n)) ⊆ NSPACE(s(n)) ⊆ TIME(2^O(s(n)))

Demo SPACE(s(n)) ⊆ TIME(2^O(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 C_M(n) = 2^O(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 C_M(n) = 2^O(s(n)) pasos.

Demo NSPACE(s(n)) ⊆ TIME(2^O(s(n))) por "reachability method". Sea M que decide L ∈ NPSPACE(s(n)):

Generar el grafo de configuracion G_M, x en tiempo 2^0(s(n))
Chequear en tiempo lineal en función del tamaño de G_M, x si C_accept es alcanzable a partir de C_start (por ej. depth-first search)

Definiciones clases espaciales

PSPACE = ⋃_c > 0 SPACE(n^c)

NPSPACE = ⋃_c > 0 NSPACE(n^c)

L = SPACE(log(n))

NL = NSPACE(log(n))

Ejemplo

3SAT ∈ PSPACE

Dado input ⌊φ⌋, buclear enumerando todas las asignaciones de variables de φ y chequear el valor de φ(z_i).

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).

Generalización: NP ⊆ PSPACE

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

PATH = {⌊G, s, t⌋ ∣ G es un grafo dirigido con camino de s a t}

PATH ∈ NL

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 q_accept si encontramos t.

Solo necesitamos guardar dos cosas en memoria:

un puntero para referirse al nodo actual: tamaño log(n)
un contador para guardar la longitud del camino visitado: tamaño log(n)

PSPACE completitud

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.

Un lenguaje PSPACE completo

Ya vimos ese truco con NP.

SPACESAT = {⌊M, w, 1ⁿ⌋ ∣ M MTD, acepta w en espacio n}

SPACESAT es PSPACE completo.

SPACESAT ∈ PSPACE: se puede decidir si x ∈ SPACESAT con una máquina universal de Turing (que usa tanto espacio como M modulo una constante multiplicativa) que verifica que M acepta w sin usar más de n espacio

Sea L ∈ PSPACE: existe M que decide L usando espacio O(n^d). Para un x ∈ {0, 1}^* construimos f(x) = ⌊M, x, 1^{n^d}⌋. Entonces L ≤ _p SPACESAT.

Quantified Boolean Formulas

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:

Q₁x₁Q₂x₂…Q_nx_n φ(x₁, x₂, …, x_n)

Asumimos que todas las variables están cuantificadas.

Una QBF es verdadera o falsa (todos los x_i 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:

∀x_iφ se reescribe en φ[x_i ← 0] ∧ φ[x_i ← 1]
∃x_iφ se reescribe en φ[x_i ← 0] ∨ φ[x_i ← 1]

Una formula booleana es una QBF sin cuantificadores existenciales.

TQBF

TQBF = {⌊φ⌋ ∣ formulas booleanas cuantificadas verdaderas }

TQBF es PSPACE completo

Stockmeyer y Meyer, Word problems requiring exponential time, 1973

TQBF ∈ PSPACE

Describimos el algoritmo A para TQBF:

Sea n el número de variables del input ψ, y m su tamaño.

Escribimos ψ[x_i = b] para ψ con x_i reemplazado por b ∈ {0, 1}.

Si n = 0 se puede evaluar ψ en tiempo (y espacio) O(m).

Si n > 0:

si ψ = ∀x_iφ: return A(φ[x_i = 0]) && A(φ[x_i = 1])
si ψ = ∃x_iφ: return A(φ[x_i = 0]) || A(φ[x_i = 1])

Sea s_n, 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 ψ[x_i = b].

s_n, m = s_{n − 1, m} + O(m) = O(n ⋅ m)

A necesita un espacio polinomial y decide TQBF.

TQBF es PSPACE hard

Mostramos que L ≤ _pTQBF para cualquier L ∈ PSPACE.

Sea M una MT decidiendo un lenguaje L y corriendo en espacio O(s(n)), y sea x ∈ {0, 1}ⁿ. La idea es construir una QBF de tamaño O(s²(n)) que es verdadera ssi M acepta x.

Una configuración de M(x) es de tamaño m = O(s(n)).

Lemma: se puede construir una formula booleana φ_M, x de tamaño O(m) tal que para C, C′ ∈ {0, 1}^m, φ_M, x(C, C′) = 1 ssi C y C′ codifican configuraciones sucesivas en el grafo de configuraciones de M(x)

Construimos ψ una QBF de tamaño polinomial tal que ψ es verdadera ssi existe un camino desde C_start hasta C_accept

Construimos una secuencia de QBF ψ_i(C, C′) verdadera ssi existe camino de longitud 2ⁱ de C a C′

Obs 1: ψ₀ = φ_M, x , ψ = ψ_m

Obs 2: hay un camino de tamaño máximo 2ⁱ de C a C′ ssi hay un camino de tamaño máximo 2^i − 1 de C a C″ y un camino de tamaño máximo 2^i − 1 de C″ a C′.

Tenemos ganas de definir:
ψ_i(C, C′) = ∃C″ ψ(C, C″) ∧ ψ(C″, C′)

Sería correcto pero ψ_m de tamaño O(2^m).

ψ_i(C, C′) = ∃C″ ∀D, E ((D = C ∧ E = C″) ∨ (D = C″ ∧ E = C′)) → ψ_i − 1(D, E)

|ψ_i| ≤ |ψ_i − 1| + O(m)

|ψ_m| ≤ O(m²)

Se puede generar ψ_m de tal forma que esté ya en forma prenexa

Observación

la demostración anda para L ∈ NPSPACE
entonces PSPACE=NPSPACE

Teorema de Savitch (1970)

Para s : ℕ ↦ ℕ constructible en espacio:

NSPACE(s(n)) ⊆ SPACE(s(n)²)

Demo Savitch

Sea L ∈ NPSPACE(S(n))
decidido por máquina cuyo grafo de config de tamaño ≤ M = 2^O(s(n))
decidir x ∈ L es equivalente a decidir si C_accept alcanzable desde C_start
definir procedimiento REACH(u, v, i) que chequea si hay camino |u → v| ≤ 2ⁱ
enumerar nodos del grafo (usa espacio O(log(M)), devolver "sí" si hay un z tal que REACH(u, z, i − 1) y REACH(z, v, i − 1).
profundidad recursiva: n
sea s_M, i el espacio usado por REACH(u, v, i)
entonces s_M, i = s_{M, i − 1} + O(logM)
entonces s_M, i = O(log²M) = O(s(n)²)

NL, L

L = SPACE(log(n))

NL = NSPACE(log(n))

¿Que se puede alojar en espacio log?

Número constante de contadores hasta la longitud del input
Número constante de puntadores hacia la cinta de input

Ejemplos

Ya vimos que PATH ∈ NL.

uPATH ∈ L (Reingold 2004)

{0^k1^k ∣ k ≥ 0} ∈ L:

contar el número de 0 y el número de 1 que están en la cinta de input. Cada contador ocupa espacio O(log(n))
comparar los dos contadores

Transductor logspace

Un transductor logspace es una máquina con 3 cintas:

de input en lectura sola
de trabajo en lectura/escritura donde el consumo de espacio es O(log(n))
de output en escritura sola: su cabezal puede o quedarse inactivo o escribir un símbolo y avanzar

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)?

Reducciones logarítmicas

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.

Composición en espacio log

Si B ≤ _LC y C ∈ L entonces B ∈ L.

Sea T el transductor logspace de la reducción, y M_C la máquina que decide C en espacio log.

Mostramos que existe M_B que decide B en espacio log.

Primer intento: armar M_B como una máquina que ejecuta T y luego M_C.

Pero eso necesita generar f(x) completamente antes de ejecutar M_C. f(x) puede ocupar más espacio que logarítmico.

Lemma:

Si T es un transductor logspace que computa x ↦ f(x), entonces existe T′ que computa ⌊x, i⌋ ↦ f(x)_i en espacio log.

Idea:
T′ tiene un contador inicializado a i.
Cuando T va para escribir un bit de f(x), T′ no escribe nada pero decementa el contador.
Cuando el contador llega a 0, T′ escribe el bit f(x)_i y se detiene.

Ese contador ocupa un espacio O(log|f(x)|) = O(log|x|)

Volviendo a la demostración de B ∈ L:

M_B controla donde está el cabezal de lectura de M_C en f(x), y ejecuta el cálculo de f(x)_i por T

Puede ser que compute varias veces el mismo bit de f(x), entonces es ineficiente en tiempo, pero es eficiente en espacio.

M_B corre en espacio O(log|f(x)|) + O(s(|x|)) + O(s′(|f(x)|)), con s y s′ el espacio de T y M_C

entonces M_B corre en espacio O(log|x|)

PATH es NL completo

sea B ∈ NL, mostramos B ≤ _LPATH

M es nondeterminista y decide B en espacio O(log(n))

usamos x ↦ f(x) = ⌊G_M, x, C_start, C_accept⌋

M(x) = 1 ssi existe camino de C_start a C_accept

x ↦ f(x) es calculable en espacio log:

representar G_M, x como matriz de adjacencia

para escribir un bit de esa matriz, computar si las configuraciones C y C′ se siguen según las funciones de transición de M

se hace en espacio O(|C| + |C′|) = O(log|x|) deterministicamente

Observaciones

un transductor logspace tiene un tiempo de corrida polinomial

entonces si B es reducible en espacio log a C, también B es reducible en tiempo polinomial a C

se puede definir NP completitud con reducciones logspace (el libro de Papadimitriou lo hace), y ¡nada se rompe!

es decir, no conocemos ningun ejemplo de problema en NP que sea completo para reducciones en tiempo polinomial, y no para reducciones en espacio log

Se puede modificar la prueba del teorema de Cook-Levin que vimos de manera que sea en espacio log

Certificados para NL

podríamos pensar que NL es la clase de problemas que tienen soluciones chequeables en espacio log

problema: SAT tiene soluciones chequeables en espacio log (no obvio pero lo asumimos)

tendríamos NP ⊆ NL, poco probable dado que NL ⊆ P

¿qué es lo que hay que arreglar en esa definición?

Definición alternativa de NL

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:

M(x, u) el output de M con x puesto en su cinta de input y u puesto en su cinta en lectura unidireccional
M corre en espacio O(log(|x|))

Equivalencia de definiciones

Mostramos que B ∈ NL_nd ⇔ B ∈ NL_cert

∃ MTND N logspace ⇔ ∃ MTD M logspace con certificado

N corre en tiempo polinomial

las elecciónes de N forman el certificado u de M

La definición de δ de M sigue las δ₀ y δ₁ de N, en particular:
δ(0, ...) = δ₀(...)
δ(1, ...) = δ₁(...)
0 o 1 siendo el bit leido por M en la cinta del certificado

dado que N usa espacio log, M también

Teorema de Immerman-Szelepcsényi

coPATH ∈ NL

Demostración

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:

n el número de nodos de G
C_i el conjunto de nodos alcanzables desde s en ≤ i pasos
c_i el tamaño de C_i

Para cualquier input, A ya sabe:

C₀ = {s}

c₀ = 1

v ∈ C_i puede ser chequeado facilmente: un certificado path_i(s, v) en lectura unidireccional es la secuencia de nodos v₀, v₁, …, v_k del camino de s a v (k ≤ i).

Además de path_i(s, v) necesitamos dos tipos de certificados:

noPath_i(s, v):
certificado para v ∉ C_i, asumiendo que el verificador ya conoce el valor c_i.
size_i(k):
certificado para c_i = k, asumiendo que el verificador ya conoce el valor c_i − 1.

Con certificados de tipo 2 nos podemos enterar de los valores c₁, …, c_n, y al final con un certificado de tipo 1, convencernos que t ∉ C_n.

Certificado noPath_i(s, v), asumiendo c_i − 1 está conocido:

v₁, path_i − 1(s, v₁), …, v_{c_i − 1}, path_i − 1(s, v_{c_i − 1})

con v₁, …v_{c_i − 1} ∈ C_i − 1.

Se puede chequear que

el número de nodos del certif. es exactamente c_i − 1
los nodos están listados en órden estrictamente creciente (para no engañar a la verificadora)
ningun de los nodos listados es v ni un vecino de v
cada certificado path_i − 1(s, v_j) es correcto

en espacio O(log(n)) con certificado en lectura unidireccional.

Certificado size_i(k), asumiendo c_i − 1 está conocido:

v₁, (no)Path_i(s, v₁), v₂, (no)Path_i(s, v₂), …, v_n, (no)Path_i(s, v_n)

dependiendo de si v ∈ C_i o no.

Se puede chequear que

los nodos están listados en órden estrictamente creciente
cada certificado path_i(s, v) o noPath_i(s, v) es correcto
el número de nodos en C_i es exactamente k

en espacio log. con certificado en lectura unidireccional.

Un certificado de (G, s, t) ∉ PATH es:

size₁(c₁), size₂(c₂), …, size_n − 1(c_n − 1), noPath_n(s, t)

Cada certificado size_i(c_i) puede ser chequeado en espacio log. y después de cada chequeo el verificador sólo necesita alojar c_i.

Entonces todo el chequeo se hace en espacio log.

Corolario

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 q_accept.

Existe un transductor T_B que computa x ↦ ⌊G_M, x, C_start, C_accept⌋ en espacio O(s(n)).

noPATH ∈ NL ie existe MTND N que decide noPATH en espacio log.

Componiendo T_B y N de manera perezosa, obtenemos M′ que decide B en espacio O(s(n)), ie, B ∈ NSPACE(s(n)).

Referencias

Arora y Barak: Capítulo 4
Sipser: Capitulo 9
Stearns, Hartmanis y Lewis. Hierarchies of memory limited computations. In FOCS, pages 179–190. IEEE, 1965.
Stockmeyer y Meyer. Word problems requiring exponential time. In STOC, pages 1–9. ACM, 1973.
Savitch. Relationships between nondeterministic and deterministic tape complexities. J. Comput. Syst. Sci., 4:177–192, 1970.
Matthew Johnson, Lectures Notes 2009
Nabil Mustafa, Lecture Notes, 2008
Immerman. Nondeterministic space is closed under complementation. SIAM J. Comput., 17(5):935–938, 1988.
Szelepcsényi. The method of forcing for nondeterministic automata. Bulletin of the European Association for Theoretical Computer Science, 33:96–100, Oct. 1987. Technical Contributions.

Complejidad Computacional Unidad 3: Complejidad espacial

Resumen Unidad 2

Preguntas

Contenido Unidad 3

SPACE

NSPACE

Precaución

Simulación universal

Space hierarchy theorem

TIME y SPACE

Configuraciónes

Grafo de configuraciones

Definiciones clases espaciales

Ejemplo

Generalización: NP ⊆ PSPACE

PATH

PSPACE completitud

Un lenguaje PSPACE completo

Quantified Boolean Formulas

TQBF

TQBF ∈ PSPACE

TQBF es PSPACE hard

Observación

Teorema de Savitch (1970)

Demo Savitch

NL, L

Ejemplos

Transductor logspace

Reducciones logarítmicas

Composición en espacio log

PATH es NL completo

Observaciones

Certificados para NL

Definición alternativa de NL

Equivalencia de definiciones

Teorema de Immerman-Szelepcsényi

Demostración

Corolario

Referencias

Complejidad Computacional
Unidad 3: Complejidad espacial