Resumen Unidad 1

Años 1960: complejidad computacional

Como los vamos a resolver

Tiempo de corrida de una máquina

Una máquina computa f o decide Lf en tiempo T(n) si su corrida en cada entrada x necesita cómo máximo T(∣x∣) pasos.

Análisis asintótico

Para comparar funciones, consideramos solamente el término más grande de una expresión, ignorando el coeficiente de ese, y los términos más chiquitos.

La razón es que con entradas de tamaño grande, sólo el termino más grande termina importando.

Ejemplo: f(n) = 6n2 + 2n2 + 20n + 45

El término de orden más grande es 6n2, y si nos abstraemos del coeficiente 6 podemos decir que f vale asipmtoticamente como máximo n3.

Escribimos f(n) = O(n3).

Notación O grande

Dadas las funciones f, g: N ↦ N. Escribimos f(n) = O(g(n)) si existen una constante c > 0 y un rango n0 ∈ N tales que para toda n > n0, f(n) ≤ c. g(n).

f(n) = O(g(n)) significa que f es menor o igual a g si no consideramos las diferencias hasta un factor constante.

Notación o chiquita

Dadas las funciones f, g: N ↦ N. Escribimos f(n) = o(g(n)) si:

limn →  + ∞(f(n) / g(n)) = 0

es decir, para cualquier c > 0, existe n0 tal que para toda n > n0, f(n) < c. g(n) .

Ejemplos o chiquita

O vs o

La O grande dice que una función no es más grande asimptóticamente que otra ( ≤ ).

La o chiquita dice que una función es menor asimptóticamente que otra ( < ).

Linear speed-up theorem (Hartmanis y Stearns, 1965)

Si f es computable por una máquina M en tiempo T(n), entonces para cualquiera constante c ≥ 1, f es computable por una máquina Mʹ en tiempo T(n) / c.

Idea: Mʹ tiene un alfabeto y conjunto de estados más grande que M.

Clases de complejidad TIME

Sea T: N ↦ N. Un lenguaje L es en TIME(T(n)) si existe una máquina que corre en tiempo cT(n) (para un c > 0) y decide L.

SPACE

Sea s: N ↦ N y L ⊆ {0, 1} * .

Decimos que L ∈ SPACE(s(n)) si existe una máquina 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 c. s(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.

TIME y SPACE

En cada paso, una máquina puede descubrir cómo máximo un número constante de casillas nuevas, entonces para cualquier f:

TIME(f(n)) ⊆  SPACE(f(n))

Configuraciones

Una configuración de una máquina es el contenido de todas las casillas no blancas de sus cintas, las posiciones de sus cabezales y su estado activo.

Si una máquina corre en espacio O(s(n)), entonces necesitamos O(s(n)) casillas para representar una de sus configuraciones.

Grafo de configuraciones

Sea M una máquina, x ∈ {0, 1} * .

El grafo de configuraciones de M, llamado GM, x, es un grafo dirigido cuyos nodos corresponden a todas las configuraciones 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 función de transición de M.


Sea M una máquina corriendo en espacio s(n). El número de configuraciones CM(n) de M con input n es acotado por:

CM(n) ≤ ∣QM∣ ⋅ n ⋅ s(n) ⋅ ∣Σ Ms(n)

con QM los estados de M, ∣Σ M su alfabeto.

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

Consecuencia: una máquina decidiendo un lenguaje en espacio s(n) no corre en más que 20(s(n)), sino entraría en un bucle infinito.

Esto nos da:

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

Clases en tiempo y en espacio

P = ⋃ c ≥ 1 TIME(nc)

EXPTIME = ⋃ c ≥ 0TIME(2nc).

PSPACE = ⋃ c > 0 SPACE(nc)

L = SPACE(log(n))

Inclusiones según el resultado anterior: dibujar díagramo de Venn.

P como clase de problemas fáciles

La clase P es robusta si cambiamos el tipo de máquina que usamos (ver resultados Unidad 1).

Doblar el tamaño del input sólo necesita k veces más tiempo (con k constante):

Con P (y arriba), no importa (tanto) el modelo

Cuando vamos a describir algoritmos para P, no vamos a describir máquinas hasta los últimos detalles.

Cuando tenemos un algoritmo en pseudocódigo cuya complejidad podemos caracterizar, podemos decir que tenemos una máquina que implementa ese mismo algoritmo, con una deceleración polinomial.

Codificación

Críticas de "P = problemas fáciles"

Lenguajes en P

(Arora and Barak, 1.8)

Algoritmo de Euclides:

E: input: x,y
   hasta que y == 0:
       a) x ← x mod y
       b) intercambiar x y
   output x

R: input: x,y
   si E(x,y) == 1 output accept
   si no, output reject       



LIN(0,1) = sistemas de inecuaciónes lineales con solución booleanas

(0-1 integer programming)

LIN(0,1)  ∈  EXPTIME (enumerar soluciones y verificar).

no se sabe si  ∈  P


No es el caso de todos los lenguajes en EXPTIME.

Clases de complejidad: inclusiones estrictas

Capitulo 9 de Sipser.

Vamos a ver resultados que implican inclusiones estrictas entre clases de complejidad:

Implican que con más recursos, se pueden resolver más problemas.

Definición preliminaria

f: N ↦ N es constructible en espacio si la función que mapea la string 1n a la representación binaria de f(n) es computable en espacio O(f(n)).
f: N ↦ N es constructible en tiempo si f(n) = O(n. logn) y si la función que mapea la string 1n a la representación binaria de f(n) es computable en tiempo O(f(n)).

Problemas arbitrariamente difíciles

Para toda función T: N ↦ N constructible en tiempo, existe un lenguaje LT decidible que no puede ser decidido por una máquina corriendo en tiempo T(n).

Demostración

LT = {⌊M⌋ ∣ M es una MT y M(⌊M⌋) = 1 en T(∣⌊M⌋∣) pasos }

Time Hierarchy Theorem (Hartmanis y Stearns, 1965)

Generalización del resultado previo:

Si f,g son funciones constructibles en tiempo tales que f(n). log(f(n)) = o(g(n)), entonces

TIME(f(n))  ⊂  ≠  TIME(g(n))

En particular: TIME(nc)  ⊂  ≠  TIME(nd) con c < d.

Aplicación

Consecuencia del time hierarchy theorem:
P  ⊂  EXPTIME

P vs EXPTIME

Space Hierarchy Theorem

Para f constructible en tiempo, existe un lenguaje L decidible en espacio O(f(n)) pero no en espacio o(f(n))

Corolario:

Para f, g constructibles en tiempo con f(n) = o(g(n)):

SPACE(f(n))  ⊂   ≠  SPACE(g(n))

Reducciones

Sipser capítulo 7.

Reducción de un lenguaje a otros.

Para que una reducción sea interesante en términos de complejidad computacional, tiene que ser barata con respeto al lenguaje de destino.

Vamos a usar las reducciones Karp en tiempo polinomial.

Reducciones

Sea A, B ⊆ {0, 1} * . A es reducible en tiempo polinomial a B, denotado A ≤ pB, si existe una función f: {0, 1} *  ↦ {0, 1} *  computable en tiempo polinomial tal que para todo x ∈ {0, 1} * , x ∈ A ssi f(x) ∈ B.


Proposiciones:

Ejercicio

Hardness y Completeness

Esas nociones indican cuando un problema representa la dificultad de la clase a cual pertenece.

NP

Un lenguaje L ⊆ {0, 1} *  está en NP ssi existe un polinomio p: N ↦ N y una MT M corriendo en tiempo polinomial tal que para todo x ∈ {0, 1} * :

   x ∈ L ↔ ∃ u ∈ {0, 1}p(∣x∣) tal que M(x, u) = 1

Lenguajes en NP

existencia de certificados cortos = pertenencia a NP:

P  ⊆  NP  ⊆  EXPTIME


P y NP

máquinas nondeterministas

Observación

Una MTND no representa cálculos fisicamente realisables.

Definición tradicional de NP

Sea T: N ↦ N y L ⊆ {0, 1} * . Decimos que L ∈  NTIME(T(n)) si existe una constante c > 0 y una TMND M en tiempo cT(n) tal que para todo x ∈ {0, 1} * :
x ∈ L ↔ M(x) = 1

NPold = ⋃ c ∈ NNTIME(nc)


Equivalencia

Las dos definiciones son equivalentes.
  1. L ∈ NPoldL ∈ NP
  2. L ∈ NPL ∈ NPold

NP hardness, completeness

Decimos que B es NP difícil (hard) si para todo A ∈  NP, A ≤ pB. Decimos que B es NP completo (complete) si B es NP difícil y está en NP.


Proposiciones:

Un lenguaje NP completo

TMSAT = {⌊M, x, 1n, 1t⌋ ∣ ∃ u ∈ {0, 1}n. M(x, u) = 1 en t pasos}

CNF-SAT

SAT  ≤ p CNF-SAT

3SAT

CNF-SAT  ≤ p 3SAT

Teorema de Cook-Levin

SAT es NP-complete

Poder expresivo booleano


Sea L ∈  NP, queremos mostrar que L ≤ pSAT.

Por definición, ∃  M corriendo en tiempo polinomial y p polinomio tal que para todo x ∈ {0, 1} * :
x ∈ L ↔ ∃ u ∈ {0, 1}p(∣x∣). M(x, u) = 1

Queremos una transformación en tiempo polinomial x ↦ φx tq:
∃ u ∈ {0, 1}p(∣x∣). M(x, u) = 1 ↔ φx ∈ SAT


Reemplazamos la verificadora M por una version que:

  1. tiene 2 cintas (con input en lectura sola)
  2. es indiferente:

Un instantáneo de M es un tuple (a, b, q) ∈ Γ 2 × Q.

Un instantáneo puede ser representado con c bits, c dependiendo de Γ  y Q (y independiente del input).

Una traza es una succesión de instantáneos.


A partir de la función de transición de M definimos:

Como M es indiferente, se pueden definir las funciones N ↦ N:

Los valores de inpos(i) and prev(i) no dependen del input y = (x, u). Además esos valores pueden ser calculados en tiempo polinomial, corriendo M con un input trivial.


Restricciones que debe cumplir una traza [z1, z2, . . . , zT(n)] para representar una corrida exitosa de M con input y:

Queremos: φx ∈ SAT ↔ ∃ u ∈ {0, 1}p(∣x∣). y = (x, u). M(y) = 1


Variables de φx:

Codificación de las restricciónes:



Tamaño de φx:

2n + 2c + 2c + (T(n) − 1)(3c + 1)23c + 1  ≤  d(n + T(n)), d ∈ N



Teorema de Cook-Levin

Dados L  ∈  NP y una string x, construimos φx tal que x ∈ L ssi φx ∈  CNF-SAT.

Idea: Sea M una verificadora de L indiferente y con 2 cintas.

φx es un "patrón de trazas" de las corridas exitosas de M con input x y u (u certificado de x).



3SAT

CNF-SAT  ≤ p 3SAT

Idea: usar regla de la resolución al revés.

Uso de la NP completitud de 3SAT

INDSET es NP completo

INDSET = {⌊(G, k)⌋ ∣ ∃ S ⊆ N(G), ∣S∣ ≥ k, ∀ uv ∈ S, uv ∉ E(G)}

INDSET  ∈  NP porque el certificado es el conjunto S.

Mostramos 3SAT  ≤ p INDSET.


Sea φ = ⋀ Ci una formula en FNC3. Sea m el número de cláusulas de φ, construimos un grafo G tal que φ⌋ ∈ 3SAT ↔ ⌊(G, m)⌋ ∈ INDSET.

Cada cláusula C de φ tiene ≤ 3 literales, entonces hay ≤ 7 asignaciones que la satisfacen.

Construimos para C un cluster de 7 nodos, marquamos cada uno con las asignaciones que satisfacen su cluster.

Conectamos dos puntos si pertenecen a clusters distintos y representan asignaciones inconsistentes (ie, 1 variables es asignada a 1 en un nodo y 0 en el otro).

Conectamos entre si todos los puntos de un mismo cluster.



VERTEXCOVER es NP completo

Reducción descrita en Sipser, teorema 7.44.

Búsqueda vs decisión

Supongamos P = NP. Para todo lenguaje L  ∈  NP y una verificadora M para L, existe una MT B corriendo en tiempo polinomial que construye un certificado para todo input x ∈ L.

Demostración:

P vs NP y NP completitud

Como manejar problemas NP-completos

EXP vs NEXP

NEXP = ⋃ c ≥ 0NTIME(2nc).

Ejercicio: encontrar la definición equivalente con certificados.

Teorema:

EXPNEXP implica PNP

Supongamos P=NP. Sea L ∈ NTIME(2nc), y M una MT para L.

Sea Lpad = {x012xc ∣ x ∈ L}. Mostramos que Lpad ∈  NP:

Entonces si P=NP, Lpad ∈ P y existe Mʹ deterministica que decide Lpad.

Entonces L ∈ EXP: para decidir si x ∈ L, lo padeamos con 012xc y vemos si esto pertenece a Lpad usando Mʹ.

El problema de la factorización

Existen problemas naturales que se sospecha estar en NP  \  P sin ser NP completos.

Factorización:

Dado n, m ∈ N tal que 1 ≤ m ≤ n, ¿ n tiene un factor d tal que 1 < d < m?

Se sospecha que FACTOR no está en P, ni es NP completo ni coNP completo.

Observación: el problema ¿ n ∈ N es un número compuesto? es una versión relajada de FACTOR y está en P (equivalentemente, PRIMES está en P).


Otros problemas en NP, sospechados de estar en NP  \  (P  ∪  NPC)

Teorema de Ladner

Si PNP, existe un lenguaje en NP  \  P que no es NP completo.

Idea: definir un problema tal que para ciertos inputs de tamaño n, el problema es resolver SAT (para que no este en P), y en otros inputs no hacer nada (para que no sea NP completo).

Prueba detallada adaptada de Arora y Barak

Jerarquia polinomial

Ver diapositivas de Nabil Mustafa.

Si P=NP, todo es la misma clase.

Conclusiones

No tenemos ninguna demostración que PNP (≠ EXPTIME) pero hoy en día se supone que NP es más dificil que P (y más fácil que EXPTIME).

Lectura

  1. Arora y Barak: Capítulo 1.6 hasta el final (P).
  2. Sipser: Capítulo 7 (P, NP)
  3. Arora y Barak 3.1, Sipser 9 (space/time hierarchy theorem)
  4. Aaronson: prueba del teorema de Cook-Levin sin usar MT indiferente (sección 5)

Referencias