Post on 05-Nov-2018
Complexity©D.Moshkovits
1
Complejidad en espacio
Complexity©D.Moshkovits
2
Motivación
Las clases de complejidad secorresponden con cotas en los recursos
Un recurso posible es el espacio: el número de casillas que una MT usa para resolver un problema
Complexity©D.Moshkovits
3
Introducción• Objetivos:
– Definir clases de complejidad en espacio• Resumen:
– Respaso de definiciones: PSPACE, NPSPACE– Las clases pequeñas: L, NL– Reducciones logarítmicas– Teorema de Savitch– Teorema de Immerman/Szelepcsenyi– Un problema completo para pspace: QBF
Complexity©D.Moshkovits
4
Las clases de complejidad en espacio
Para cualquier función f:N→N, se define:
SPACE(f(n))={L | L es un lenguaje reconocido por una MTD que trabaja en espacio O(f(n))}
NSPACE(f(n))={L | L es un lenguaje reconocido por una MTND que trabaja en espacio
O(f(n))}}
Complexity©D.Moshkovits
5
Las clases de complejidad en espacio
Uk
knSPACEPSPACE )(=Uk
knSPACEPSPACE )(=
Uk
knNSPACENPSPACE )(=Uk
knNSPACENPSPACE )(=
Complexity©D.Moshkovits
6
Las clases pequeñas: enespacio logarítmico
Uk
nkSPACEL ))log((=Uk
nkSPACEL ))log((=
Uk
nkNSPACENL ))log((=Uk
nkNSPACENL ))log((=
Complexity©D.Moshkovits
7
¡Problema!¿Cómo puede una MT usar
log(n) si la entrada yaocupa n casillas?
Complexity©D.Moshkovits
8
Máquinas con 3 cintas
_bbabaa
__bbbbb . . .
__abaab
entrada
trabajo
salida
Sólo lectura
Sólo escritura
Lectura/escritura
Para definir las clases en espacio sólo se cuentan las casillas de esta cinta
. . .
. . .
Complexity©D.Moshkovits
9
Ejemplo
Cuestión: ¿Cuánto espacio requiere una MTD que decida {anbn | n>0} ?
Nota: para contar n necesitamos log(n) bits
Complexity©D.Moshkovits
10
Accesibilidad en un Grafo
ACCES• Entrada: un grafo dirigido G=(V,E) y
dos nodos s,t∈V• Problema: decidir si existe un camino
desde s hasta t in G
Complexity©D.Moshkovits
11
Accesibilidad en un Grafo
ts
Complexity©D.Moshkovits
12
ACCES está en NL• Comenzar en s• No determinísticamente elegir un
nodo vecino al cual saltar • Aceptar si y sólo si llegas a t
• Contar |V| en binario requiere espacio log|V|
• Guardar el nodo actual requiere log|V|
Complexity©D.Moshkovits
13
Configuraciones¿Cuáles son los objetos que determinan
una configuración de una MT?
• El contenido de la cinta de trabajo• El estado de la máquina• La posición de la cabeza en la cinta de entrada• La posición de la cabeza en la cinta de trabajo• La posición de la cabeza en la cinta de salida
Si la MT usa espacio logarítmicohay un número polinómico de
configuraciones
Complexity©D.Moshkovits
14
Reducciones en espacio logarítmico
Definición:A se reduce con una reducción en espacio
logarítmico a B, se escribe A≤LB, si existe una MTD que trabaja en espaciologarítmico y que, dada la entrada w, devuelve f(w) t.q.
w∈A si y sólo si f(w)∈B
La reducción
Complexity©D.Moshkovits
15
¿Es útil la noción de reducciónlogarítmica?
Supongamos que A1 ≤L A2 y que A2∈L; ¿Cómo construir una MTD que trabaje en espacio
logarítmico y que decida A1?
Solución incorrecta:
w
¡Demasiado largo!f(w)
Usar la MTD para A2 y que decida si f(w)∈A2
Complexity©D.Moshkovits
16
Reducciones logarítmicasLema: si
1. A1 ≤L A22. A2 ∈ L
entonces, A1 está en L
– f es la reducción logarítmica- M es la máquina logarítmica para A2
Prueba: entrada x (para decidir si está en A1):Simular M ysiempre que M lea el i-ésimo símbolo de sucinta de entrada, computar f(x) y esperar que el i-ésimo bit salga en la cinta de entrada
Complexity©D.Moshkovits
17
NL Completitud
Definición:Un lenguaje B is NL-Completo si1. B∈NL2. Por cada A∈NL, A≤LB.
Si se da (2), B es NL-hard
Complexity©D.Moshkovits
18
Teorema de Savitch
Teorema 1:∀S(n) ≥ log(n)
NSPACE(O(S(n))) ⊆ SPACE(O(S(n)2))Prueba:
Primero probaremos que NL⊆SPACE(O(log2(n)))
Después veremos que esto implica el caso general
Complexity©D.Moshkovits
19
Teorema de Savitch
Teorema 2:NSPACE(O(log(n))) ⊆SPACE(O(log2(n)))
Prueba:1. Primero probaremos que ACCES es NL-
completo (bajo la reducción logarítmica)2. Después mostraremos un algoritmo que
decide ACCES en espacio O(log2(n)).
Complexity©D.Moshkovits
20
ACCES es NL-Completo
Teorema 3: ACCES es NL-Completo
Prueba: con la siguiente reducción:
st≤L
“¿Hay un caminode s a t?”
“¿M accepta x?”
Complexity©D.Moshkovits
21
Aspecto técnico
Observación:Sin pérdida de generalidad podemos
considerar que toda MTND tiene una única configuración aceptadora.
Complexity©D.Moshkovits
22
Grafo de configuracionesLa computación de una MTND M sobre entrada
x puede ser descrita por el grafo GM,x:
Un nodo por cada configuraciónLa configuración
inicial
s t
La configuración aceptadora
(u,v)∈E si M puede pasarde la configuración u a la v
Complexity©D.Moshkovits
23
La reducción es correcta
Por cada MTND M y cada entrada x, Macepta x si y sólo si existe un camino de s a t en GM,x
Complexity©D.Moshkovits
24
ACCES es NL-Completo
Teorema 3: ACCES es NL-CompletoPrueba: Hemos visto que ACCES está en
NL. Hemos visto que cualquier lenguaje de NL se reduce a ACCES y la reducción es computable en espacio logarítmico
¿Por qué?
Complexity©D.Moshkovits
25
Un hecho conocido
Hecho: NL⊆POtra prueba:• Cualquier lenguaje de NL se L-reduce
a ACCES• Cualquier lenguaje de NL se p-reduce
a ACCES• ACCES is in P• Entonces, cualquier lenguaje de NL
está en P.
Complexity©D.Moshkovits
26
¿Qué más?
Necesitamos demostrar que ACCES se puede decidir con una MTD en espacioO(log2(n)).
Complexity©D.Moshkovits
27
El truco“Si hay un camino, de longitud d, de u a v ”“existe un nodo z, de forma que, hay un camino de u a z de longitud d/2 y otro
camino de z a v de longitud d/2”
d/2 d/2
u v . . .z
d
Complexity©D.Moshkovits
28
Reciclando el espacio
Las dos llamadas recursivas pueden usar el mismo espacio
Complexity©D.Moshkovits
29
El algoritmoBoolean PATH(a,b,d) {
if there is an edge from a to b then return TRUE
else {if d=1 return FALSEfor every vertex v {
if PATH(a,v, d/2) and PATH(v,b, d/2)then return TRUE
} return FALSE
}}
Complexity©D.Moshkovits
30
Ejemplo del algoritmo de savitchboolean PATH(a,b,d) {
if there is an edge from a to b thenreturn TRUE
else {if (d=1) return FALSEfor every vertex v (not a,b) {
if PATH(a,v, d/2) and PATH(v,b, d/2) thenreturn TRUE
}return FALSE
}}
boolean PATH(a,b,d) {if there is an edge from a to b then
return TRUEelse {
if (d=1) return FALSEfor every vertex v (not a,b) {
if PATH(a,v, d/2) and PATH(v,b, d/2) thenreturn TRUE
}return FALSE
}}
boolean PATH(a,b,d) {if there is an edge from a to b then
return TRUEelse {
if (d=1) return FALSEfor every vertex v (not a,b) {
if PATH(a,v, d/2) and PATH(v,b, d/2) thenreturn TRUE
}return FALSE
}}
boolean PATH(a,b,d) {if there is an edge from a to b then
return TRUEelse {
if (d=1) return FALSEfor every vertex v (not a,b) {
if PATH(a,v, d/2) and PATH(v,b, d/2) thenreturn TRUE
}return FALSE
}}
boolean PATH(a,b,d) {if there is an edge from a to b then
return TRUEelse {
if (d=1) return FALSEfor every vertex v (not a,b) {
if PATH(a,v, d/2) and PATH(v,b, d/2) thenreturn TRUE
}return FALSE
}}
boolean PATH(a,b,d) {if there is an edge from a to b then
return TRUEelse {
if (d=1) return FALSEfor every vertex v (not a,b) {
if PATH(a,v, d/2) and PATH(v,b, d/2) thenreturn TRUE
}return FALSE
}}
boolean PATH(a,b,d) {if there is an edge from a to b then
return TRUEelse {
if (d=1) return FALSEfor every vertex v (not a,b) {
if PATH(a,v, d/2) and PATH(v,b, d/2) thenreturn TRUE
}return FALSE
}}
boolean PATH(a,b,d) {if there is an edge from a to b then
return TRUEelse {
if (d=1) return FALSEfor every vertex v (not a,b) {
if PATH(a,v, d/2) and PATH(v,b, d/2) thenreturn TRUE
}return FALSE
}}
boolean PATH(a,b,d) {if there is an edge from a to b then
return TRUEelse {
if (d=1) return FALSEfor every vertex v (not a,b) {
if PATH(a,v, d/2) and PATH(v,b, d/2) thenreturn TRUE
}return FALSE
}}
boolean PATH(a,b,d) {if there is an edge from a to b then
return TRUEelse {
if (d=1) return FALSEfor every vertex v (not a,b) {
if PATH(a,v, d/2) and PATH(v,b, d/2) thenreturn TRUE
}return FALSE
}}
boolean PATH(a,b,d) {if there is an edge from a to b then
return TRUEelse {
if (d=1) return FALSEfor every vertex v (not a,b) {
if PATH(a,v, d/2) and PATH(v,b, d/2) thenreturn TRUE
}return FALSE
}}
boolean PATH(a,b,d) {if there is an edge from a to b then
return TRUEelse {
if (d=1) return FALSEfor every vertex v (not a,b) {
if PATH(a,v, d/2) and PATH(v,b, d/2) thenreturn TRUE
}return FALSE
}}
boolean PATH(a,b,d) {if there is an edge from a to b then
return TRUEelse {
if (d=1) return FALSEfor every vertex v (not a,b) {
if PATH(a,v, d/2) and PATH(v,b, d/2) thenreturn TRUE
}return FALSE
}}
boolean PATH(a,b,d) {if there is an edge from a to b then
return TRUEelse {
if (d=1) return FALSEfor every vertex v (not a,b) {
if PATH(a,v, d/2) and PATH(v,b, d/2) thenreturn TRUE
}return FALSE
}}
4
32
1
(a,b,c)=hay un camino desde a hasta b en menos de c pasos.
(1,4,3)(1,4,3)(1,2,2)(1,4,3)(1,2,2)TRUE(1,4,3)(2,4,1)(1,4,3)(2,4,1)FALSE(1,4,3)(1,3,2)(1,4,3)(1,3,2)(1,2,1)(1,4,3)(1,3,2)(1,2,1)TRUE(1,4,3)(1,3,2)(2,3,1)(1,4,3)(1,3,2)(2,3,1)TRUE(1,4,3)(1,3,2)TRUE(1,4,3)(3,4,1)(1,4,3)(3,4,1)TRUE(1,4,3) TRUE
O(log(d))
Complexity©D.Moshkovits
31
MTD en espacio en O(log2(n))
Teorema 4: existe una MTD que decide ACCES en espacio O(log2(n)).
Prueba:Para decidir ACCES, se invoca PATH(s,t,|V|)
La complejidad en espacio es: O(log2(n))
Complexity©D.Moshkovits
32
Conclusión
Theorem 2:NSPACE(O(log(n))) ⊆SPACE(O(log2(n)))
¿Qué ocurre con el caso general NSPACE(O(S(n)))⊆SPACE(O(S2(n)))?
Complexity©D.Moshkovits
33
La técnica de “relleno”Motivación: generalización de propiedades
Tenemos:espacio O(log(n)) puede ser simulado por… espacio O(log2(n))
+ no-determinismo + determinismo
Queremos:puede ser simulado por…espacio O(s(n)) espacio O(s(n)2)
+ no-determinismo + determinismo
Complexity©D.Moshkovits
34
Formalmente
Lema: Para cada función constructible en espacios1(n), s2(n)≥log(n), f(n)>n:
si(n) puede ser computada en espacio si(n)
NSPACE(O(s1(n))) ⊆ SPACE(O(s2(n)))
⇓NSPACE(O(s1(f(n)))) ⊆ SPACE(O(s2(f(n))))
p.e. NSPACE(O(n))⊆SPACE(O(n2)) ⇒ NSPACE(O(n2))⊆SPACE(O(n4))
Complexity©D.Moshkovits
35
Idea
MTND...n
epacio: O(s1(f(n)))
...
......
f(n)MTD
espacio: O(s2(f(n)))10
...
0
espacio: s1(.) en eltamaño de su entrada
n
Complexity©D.Moshkovits
36
La técnica de “relleno”• Sea L∈NPSPACE(O(s1(f(n))))• Existe una MTND de 3-cintas ML:
babba������������������������
|x|
Entrada
Trabajo ���������������������������
O(s1(f(|x|)))
Complexity©D.Moshkovits
37
• Sea L’ = { x10f(|x|)-|x|-1 : x∈L }• Vemos que existe una MTND ML’ que decide L’
en el mismo número de casillas que ML.
O(s1(f(|x|))
La técnica de “relleno”
Entrada
Trabajo
f(|x|)
babba100000000000000000000000000000000���
���������������������������
Complexity©D.Moshkovits
38
1. Separar x buscando el último 1.2. Simular ML sobre x.
La técnica de “relleno” – ML’
Entrada
Trabajo
babba100000000000000000000000000000000���
En espacio O(log(f(|x|))
en espacio O(s1(f(|x|)))
f(|x|)
���������������������������
O(s1(f(|x|)))
Complexity©D.Moshkovits
39
La técnica de “relleno”
f(|x|)
O(s1(f(|x|)))
espacio total: O(s1(f(|x|)))
Entrada babba100000000000000000000000000000000���
���������������������������Trabajo
Complexity©D.Moshkovits
40
La técnica de “relleno”
• Comenzamos con L∈NSPACE(O(s1(f(n))))
• Vemos que: L’∈NSPACE(O(s1(n)))• Entonces, L’∈SPACE(O(s2(n)))• Usando la MTD para L’, podemos
construir una MTD para L, que trabaja en espacio O(s2(f(n))).
Complexity©D.Moshkovits
41
La técnica de “relleno”
• La MTD para L simulará la MTD paraL’ cuando trabaja con entradas concatenadas con 1000000...
babba���Entrada
100000000000000000000000
Complexity©D.Moshkovits
42
La técnica de “relleno”• Guardar la posición del último bit de la entrada.
Esto requiere espacio O(log(f(|x|))).• Interpretar aue a partir de ahí hay una cadena
10000000000000…• Simular en espacio O(s2(f(|x|))).
⇒NSPACE(O(s1(f(n))))⊆SPACE(O(s2(f(n))))
Complexity©D.Moshkovits
43
Versión general del teoremade Savitch
Teorema 1:∀S(n) > log(n)
NSPACE(O(S(n))) ⊆ SPACE(O(S(n)2))
Prueba Hemos probado queNL⊆SPACE(O(log2(n))). El teoremageneral se obtiene aplicando el argumentode “relleno”.
Complexity©D.Moshkovits
44
Corolario
Corolario: PSPACE = NPSPACE
Prueba:Trivialmente tenemos
PSPACE⊆NPSPACE. Por el teorema de Savitch,
NPSPACE⊆PSPACE.
Complexity©D.Moshkovits
45
Espacio “versus” Tiempo• Hemos visto que las clases de complejidad
en espacio no se comportan como las clasesde complejiad en tiempo: – El no determinismo no influye drásticamente
cuando hablamos de espacio (Savitch).• Vamos a ver otra diferencia:
– El no determinismo, cuando hablamos de espacio, es cerrado por complementario(Immerman/Szelepcsenyi).
Complexity©D.Moshkovits
46
NO-ACCESNO-ACCES• Entrada: un grafo dirigido G=G(V,E) y
dos nodos s,t∈V.• Problema: decidir si no existe camino
de s a t.
Complexity©D.Moshkovits
47
NO-ACCES
• Claramente, NO-ACCES es coNL-Complete.(porque ACCES es NL-Complete(*). Si
demostramos que NO-ACCES también estáen NL(*), entonces NL=coNL.
(*) Ver el tema relativo a coNP
Complexity©D.Moshkovits
48
Un algoritmo para NO-ACCES
1. Cuenta el número de nodos que sonaccesibles desde s.
2. Elimina t del grafo y cuenta de nuevo3. Acepta si los dos número son el
mismo.
Veremos un algoritmo no determinista, en espacio logarítmico, para contar el número de nodos accesibles
Complexity©D.Moshkovits
49
Algoritmo no determinista para contar el número de nodos
PAP 151-153
• El algoritmo tiene cuatro iteraciones • La más superficial:
|S(0)| := 1para cada k desde 1..(n-1)
calcular |S(k)| a partir de |S(k-1)|
Número de nodos accesibles desde s con un
camino de longitud ≤ k
Complexity©D.Moshkovits
50
|S(k)| a partir de |S(k-1)|C := 0para cada nodo u del grafo
si u ∈ S(k) entonces C:= C+1fin si
fin para
Complexity©D.Moshkovits
51
m := 0 ; respuesta := falsepara cada nodo v del grafo
si v ∈ S(k-1) entonces m:= m+1
si (v, u) ∈ Eentonces respuesta:= truefin si
fin sifin parasi m < |S(k-1)| entonces rechaza
si no devuelve respuestafin si
u ∈ S(k)
Paso no determinista
Complexity©D.Moshkovits
52
v ∈ S(k-1)w0:= s para cada p desde 1..(k-1)
adivinar un nodo wpsi (wp-1, wp) ∉ Eentonces rechazafin si
fin parasi wk-1 = v entonces devuelve true
si no rechazafin si
Complexity©D.Moshkovits
53
Coste del algoritmoLemma: El algoritmo usa espacio O(log(n)).Prueba:Hay un número constante de variables
( k, |S(k-1)|, C, u, m, v, p, wp-1, wp)La máquina tiene cintas separadas para
cada variable, que se incrementan y/o se comparan. Esto requiere espacioO(log(n)).
Complexity©D.Moshkovits
54
Teorema de ImmermanTeorema:[Immerman/Szelepcsenyi]: NL=coNLPrueba:(1) NO-ACCES es NL-Complete(2) NO-ACCES∈NLPor tanto, NL=coNL.
Complexity©D.Moshkovits
55
Corolario
Corolario:∀s(n)≥log(n),
NSPACE(O(s(n)))=coNSPACE(O(s(n)))
Prueba: Aplicando la técnica de “relleno”.
Complexity©D.Moshkovits
56
QBF
• Vamos a encontrar un problema que es completo para PSPACE.
• Este problema se llama QBF: laversión cunatificada de SAT.
Complexity©D.Moshkovits
57
QBF
• Entrada: una fórmula booleana φcuantificada y sin variables libres
• Problema: decidir si φ es satisfactible
Ejemplo: una fórmula booleana completamente cuantificada
∀x∃y∀z[(x∨¬y∨z)∧(¬x∨y)]∀x∃y∀z[(x∨¬y∨z)∧(¬x∨y)]
Complexity©D.Moshkovits
58
QBF está en PSPACE
Teorema: QBF∈PSPACEPrueba: describimos un algoritmo A para
evaluar φ:• Si φ no tiene cuantificadores: evaluarla• Si φ=∀x(ψ(x)) llamar a A sobre ψ(T) y
sobre ψ(F); Aceptar si ambas llamadas evaluan a true.
• Si φ=∃x(ψ(x)) llamar a A sobre ψ(T) ysobre ψ(F); Aceptar si alguna es true.
en tiempo polinómico
Complexity©D.Moshkovits
59
Algoritmo para QBF
T ∀x∃y[(x∨¬y)∧(¬x∨y)]∀x∃y[(x∨¬y)∧(¬x∨y)]
∃y[(F∨¬y)∧(¬F∨y)]∃y[(F∨¬y)∧(¬F∨y)] ∃y[(T∨¬y)∧(¬T∨y)]∃y[(T∨¬y)∧(¬T∨y)]
(F
T T
∨¬F)∧(¬F∨F)(F∨¬F)∧(¬F∨F) (F∨¬T)∧(¬F∨T)(F∨¬T)∧(¬F∨T) (T∨¬T)∧(¬T∨T)(T∨¬T)∧(¬T∨T)(T∨¬F)∧(¬T∨F)(T∨¬F)∧(¬T∨F)
T F F T
Complexity©D.Moshkovits
60
Coste en espacio
• Como las dos llamadas recursivas pueden usar el mismo espacio,
• el espacio total que se necesita es polinómico en el número de variables (laprofundidad del árbol de llamadas)
⇒ QBF se puede decidir en espacio polinómico.
Complexity©D.Moshkovits
61
PSPACE Completitud
Definición:Un lenguaje B es PSPACE-Completo si1. B∈PSPACE2. Por cada A∈PSAPCE, A≤PB.
reducción de Karp
si no se verifica (2), entonces B esPSPACE-Hard
Complexity©D.Moshkovits
62
QBF es PSPACE-Completo
Teorema: QBF es PSAPCE-CompletoPrueba: Queda demostrar que QBF es
PSPACE-Hard:
≤P∀x1∃x2∀x3…[…]∀x1∃x2∀x3…[…]
“ M acepta x en espacio polinómico”
“la fórmula es satisfactible”
Complexity©D.Moshkovits
63
QBF es PSPACE-Hard
Dada una MTD M para un lenguaje L∈ PSPACE yuna entrada x, sea
fM,x(u, v)la función que, por cada dos configuraciones u y
v, devuelve TRUE si y sólo si M sobre entradax se mueve desde la configuración u hasta laconfiguración v
fM,x(u, v) se puede calcular rápidamente
Complexity©D.Moshkovits
64
Formulación de la conectividad
La siguiente fórmula, sobre variables u,v∈V ylongitud del camino d, devuelve TRUE si y sólo si G tiene un camino de u a v de longitud ≤d
φ(u,v,1) ≡ fM,x(u, v) ∨ u=vφ(u,v,d) ≡ ∃w∀x∀y[((x=u∧y=w)∨(x=w∧y=v))→φ(x,y,d/2)]
w es accesible desde u en d/2 pasos. v es accesible
desde w en d/2 pasos.simula AND de φ(u,w,d/2)
y φ(w,v,d/2)
Complexity©D.Moshkovits
65
QBF es PSPACE-CompletoTeorema: QBF es PSPACE-CompletoPrueba:φ ≡ φ(s,t,|V|) es TRUE si y sólo si hay un camino de s
a t.φ se puede construir en tiempo polinómico.Entonces, cualquier lenguaje de PSPACE es p-reducible a QBF, es decir, QBF es PSPACE-Hard.Como QBF∈PSPACE ⇒ PSPACE-Completo.
Complexity©D.Moshkovits
66
Resumen
• Hemos introducido una nueva forma de clasificar problemas, según lacantidad de espacio requerida en la computación.
• Hemos definido varias clases de complejidad: L, NL, PSPACE.
Complexity©D.Moshkovits
67
Resumen
• Los resultados más importantes presentados son:– ACCES es NL-Completo– QBF es PSPACE-Completo– Teorema de Savitch (NL⊆SPACE(O(log2(n))))– La técnica de relleno– Teorema de Immerman (NL=coNL)