Página de Guillaume Hoffmann

View on GitHub

% Complejidad Computacional
Unidad 2: Clases de complejidad

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 $L_f$ 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)= 6n^2 + 2n^2 + 20n + 45$

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

Escribimos $f(n) = O(n^3)$.

Notación O grande

Dadas las funciones $f,g : \mathbb{N} \mapsto \mathbb{N}$. Escribimos $f(n) = O(g(n))$ si existen una constante $c > 0$ y un rango $n_0 \in \mathbb{N}$ tales que para toda $n > n_0$, $f(n) \leq 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 : \mathbb{N} \mapsto \mathbb{N}$. Escribimos $f(n) = o(g(n))$ si: $lim_{n \rightarrow +\infty} (f(n)/g(n))=0$ es decir, para cualquier $c > 0$, existe $n_0$ tal que para toda $n>n_0$, $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 ($\leq$).

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 \geq 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: \mathbb{N} \mapsto \mathbb{N}$. Un lenguaje $L$ es en **TIME**(T(n)) si existe una máquina que corre en tiempo $c⋅T(n)$ (para un $c > 0$) y decide $L$.

SPACE

Sea $s:\mathbb{N}\mapsto{N}$ y $L\subseteq \{0,1\}^*$. Decimos que $L\in$**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)) \subseteq$ **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\in{0,1}^*$.

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

Sea M una máquina corriendo en espacio $s(n)$. El número de configuraciones $C_M(n)$ de $M$ con input $n$ es acotado por: $C_M(n) \leq |Q_M| \cdot n \cdot s(n) \cdot |\Sigma_M|^{s(n)}$ con $|Q_M|$ los estados de $M$, $|\Sigma_M|$ su alfabeto. En particular si $s(n) \geq log(n)$ tenemos $C_M(n) = 2^{O(s(n))}$.

Consecuencia: una máquina decidiendo un lenguaje en espacio $s(n)$ no corre en más que $2^{0(s(n))}$, sino entraría en un bucle infinito.

Esto nos da:

**TIME**$(s(n))$ $\subseteq$ **SPACE**(s(n)) $\subseteq$ **TIME**$(2^{O(s(n))})$

Clases en tiempo y en espacio

**P** = $\bigcup_{c \geq 1}$ **TIME**$(n^c)$ **EXPTIME** = $\bigcup_{c \geq 0}$**TIME**$(2^{n^c})$. **PSPACE** = $\bigcup_{c>0}$ **SPACE**$(n^c)$ **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) $\in$ EXPTIME (enumerar soluciones y verificar).

no se sabe si $\in$ 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: \mathbb{N} \mapsto \mathbb{N}$ es *constructible en espacio* si la función que mapea la string $1^n$ a la representación binaria de $f(n)$ es computable en espacio $O(f(n))$.
$f: \mathbb{N} \mapsto \mathbb{N}$ es *constructible en tiempo* si $f(n) = O(n . log n)$ y si la función que mapea la string $1^n$ a la representación binaria de $f(n)$ es computable en tiempo $O(f(n))$.

Problemas arbitrariamente difíciles

Para toda función $T: \mathbb{N} \mapsto \mathbb{N}$ constructible en tiempo, existe un lenguaje $L_T$ decidible que *no* puede ser decidido por una máquina corriendo en tiempo $T(n)$.

Demostración

$L_T = { \lfloor M \rfloor \mid M$ es una MT y $M(\lfloor M \rfloor) =1$ en $T(|\lfloor M \rfloor|)$ 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))$ $\subset \neq$ **TIME**$(g(n))$

En particular: TIME($n^c$) $\subset \neq$ TIME($n^d$) con $c < d$.

Aplicación

Consecuencia del time hierarchy theorem:

**P** $\subset$ **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)$) $\subset$ $\neq$ **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\subseteq\{0,1\}^*$. A es *reducible en tiempo polinomial* a $B$, denotado $A \leq_{p} B$, si existe una función $f:\{0,1\}^* \mapsto \{0,1\}^*$ computable en tiempo polinomial tal que para todo $x\in\{0,1\}^*$, $x \in A$ ssi $f(x)\in B$.


Proposiciones: * si $A \leq_p B$ y $B \in$ **P** entonces $A \in$ **P** * $\leq_p$ es transitiva

Ejercicio

Hardness y Completeness

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

NP

Un lenguaje $L \subseteq \{0,1\}^*$ está en **NP** ssi existe un polinomio $p: \mathbb{N} \mapsto \mathbb{N}$ y una MT M corriendo en tiempo polinomial tal que para todo $x \in \{0,1\}^*$: $~ ~ ~ x \in L \leftrightarrow \exists u \in \{0,1\}^{p(|x|)} ~$ tal que $~ M(x,u)=1$
  • M se llama la verificadora de $L$, y $u$ un certificado de $x$ (con respeto a $L$ y M).
  • La definición de NP es asimétrica!

Lenguajes en NP

existencia de certificados cortos = pertenencia a NP:

P $\subseteq$ NP $\subseteq$ EXPTIME

* **P** $\subseteq$ **NP** * **NP** $\subseteq$ **EXPTIME**


  • No se sabe si P ≠ NP, ni si NP ≠ EXPTIME.

P y NP

máquinas nondeterministas

  • Una MTND tiene $\delta_0$ and $\delta_1$ y un estado especial $q_{accept}$.
  • En cada paso, una MTND hace una elección arbitraria entre las dos funciones de transición.
  • Para un input $x$, si existe una secuencia de esos pasos (elecciones nondeterminísticas) que hace que M alcanza $q_{accept}$, decimos que $M(x) = 1$.
  • Si toda secuencia de elecciones hace que M se detiene sin alcanzar $q_{accept}$, decimos que $M(x)=0$.
  • M corre en tiempo $T(n)$ si para todo input $x\in{0,1}^*$ y toda secuencia de elecciones nondeterminísticas, M alcanza $q_{halt}$ o $q_{accept}$ dentro de $T(|x|)$ pasos.

Observación

Una MTND no representa cálculos fisicamente realisables.

Definición tradicional de NP

Sea $T: \mathbb{N} \mapsto \mathbb{N}$ y $L\subseteq \{0,1\}^*$. Decimos que $L \in$ **NTIME**$(T(n))$ si existe una constante $c>0$ y una TMND M en tiempo $c⋅T(n)$ tal que para todo $x\in \{0,1\}^*$: $$x\in L \leftrightarrow M(x)=1$$ $NP_{old} = \bigcup_{c\in \mathbb{N}}$**NTIME**$(n^c)$


Equivalencia

Las dos definiciones son equivalentes.
  1. $L \in NP_{old}$ → $L \in NP$
    • si existe una MTND M que decide $L$, se puede construir una MTD $M’$ que, con input $(x,u)$ y $u$ de longitud adecuada, simula una computación de $M$ con input $x$ eligiendo $\delta_{u[n]}$ en cada paso $n$.
  2. $L \in NP$ → $L \in NP_{old}$
    • se puede construir una MTND que, con input $x$, genera un certificado en $p(|x|)$ pasos de manera nondeterministica, y luego lo averigua con la verificadora de $L$.

NP hardness, completeness

Decimos que B es **NP** difícil (hard) si para todo $A\in$ **NP**, $A \leq_p B$. Decimos que $B$ es **NP** completo (complete) si $B$ es **NP** difícil y está en **NP**.


Proposiciones: * si L es **NP** difícil y L $\in$ **P**, entonces **P** = **NP** * si L es **NP** completo, entonces L $\in$ **P** ssi **P** = **NP**.

Un lenguaje NP completo

TMSAT = ${ \lfloor M, x, 1^n, 1^t \rfloor \mid \exists u\in{0,1}^n . M(x,u)=1$ en t pasos$}$

  • TMSAT $\in$ NP: la verificadora de N es una máquina universal de Turing que simula M con input (x,u) y verifica que su output es 1 despues de $t$ pasos. Su corrida es polinomial en función de su input porque se puede simular máquinas con una desaceleración polinomial.
  • Sea L $\in$ NP. Existe verificadora M corriendo en tiempo polinomial $q(n)$, y existe un polinomio $p(n)$ que determine el tamaño de los certificados. Entonces a toda $x\in L$ le asociamos la string $\lfloor M, x, 1^{p(n)}, 1^{q(n+p(n))}\rfloor$ con n = |x|

CNF-SAT

**SAT** $\leq_p$ **CNF-SAT**

3SAT

**CNF-SAT** $\leq_p$ **3SAT**

Teorema de Cook-Levin

SAT es NP-complete

Poder expresivo booleano

Sea $L \in$ NP, queremos mostrar que $L \leq_{p} SAT$.

Por definición, $\exists$ M corriendo en tiempo polinomial y $p$ polinomio tal que para todo $x \in {0,1}^*$: \(x \in L \leftrightarrow \exists u \in \{0,1\}^{p(|x|)} . M(x,u)=1\)

Queremos una transformación en tiempo polinomial $x \mapsto \varphi_x$ tq: \(\exists u \in \{0,1\}^{p(|x|)} . M(x,u)=1 \leftrightarrow \varphi_x \in SAT\)

Reemplazamos la verificadora M por una version que:

  1. tiene 2 cintas (con input en lectura sola)
  2. es indiferente:
    • las corridas de M toman el mismo tiempo para todo input de tamaño $n$
    • la ubicación de los cabezales de M en un paso $i$ sólo dependen del tamaño del input y de $i$

Un instantáneo de M es un tuple $(a,b,q) \in \Gamma^2 \times Q$.

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

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

  • ¿Cuales son las condiciones que debe cumplir una traza para representar una corrida exitosa de M con input $(x,u)$?
  • Vamos a construir $\varphi_x$ como un patrón de traza que es satisfacible si y sólo si existe un $u$ tal que $M(x,u) =1$

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

Como M es indiferente, se pueden definir las funciones $\mathbb{N}\mapsto\mathbb{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 $[z_1,z_2,…,z_{T(n)}]$ para representar una corrida exitosa de M con input $y$:

Queremos: $\varphi_x \in SAT \leftrightarrow \exists u \in {0,1}^{p(|x|)} . y = (x,u) . M(y)=1$

Variables de $\varphi_x$:

Codificación de las restricciónes:

Tamaño de $\varphi_x$:

$2n + 2c + 2c + (T(n)-1)(3c+1)2^{3c+1}$ $\leq$ $d(n + T(n))$, $d \in \mathbb{N}$

Teorema de Cook-Levin

Dados L $\in$ NP y una string $x$, construimos $\varphi_x$ tal que $x\in L$ ssi $\varphi_x \in$ CNF-SAT.

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

$\varphi_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** $\leq_p$ **3SAT**

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

Uso de la NP completitud de 3SAT

INDSET es NP completo

INDSET = ${\lfloor (G,k) \rfloor \mid\exists S\subseteq N(G),|S|\geq k,\forall uv\in S, uv\not\in E(G)}$

INDSET $\in$ NP porque el certificado es el conjunto $S$.

Mostramos 3SAT $\leq_p$ INDSET.

Sea $\varphi = \bigwedge C_i$ una formula en FNC3. Sea $m$ el número de cláusulas de $\varphi$, construimos un grafo $G$ tal que $\lfloor \varphi \rfloor \in 3SAT \leftrightarrow \lfloor (G,m) \rfloor \in INDSET$.

Cada cláusula $C$ de $\varphi$ 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.

  • La transformación se puede hacer en tiempo polinomial.
  • $\varphi$ satisfacible
    → existe asignación $z$ tal que $\varphi(z)=1$
    → definir $S$ los nodos de cada cluster que corresponden a la restriccion de $z$ a las variables del cluster
    → hay $m$ nodos no conectados entre si en $G$
  • hay $m$ nodos no conectados entre si en $G$
    → pertenecen a clusters distintos
    → las asignaciones parciales que esos nodos representan son consistentes
    → con ellas construimos $z$ tal que $\varphi(z)=1$
    → $\varphi$ satisfacible

VERTEXCOVER es NP completo

Reducción descrita en Sipser, teorema 7.44.

Búsqueda vs decisión

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

Demostración:

P vs NP y NP completitud

  • 1956: Kurt Gödel escribe una carta a John von Neumann planteándole la posibilidad de decidir en tiempo polinomial si una formula de primer order tiene una prueba de longitud $n$
  • 1971: Cook “The Complexity of Theorem Proving Procedures”
  • 1972: Karp “Reducibility Among Combinatorial Problems”
  • 1972: Miller and Thatcher, editors. “Complexity of computer computations”. Plenum Press: proceedings de la conferencia donde se presentó el artículo de Karp frente a 200 investigadores en computación (según el deseo de Michael Rabin)
  • 1971/3: Levin “Универсальные задачи перебора” (Universal search problems)

Como manejar problemas NP-completos

  • Heuristicas: NP es acerca de todos los inputs posibles, mientras que en casos concretos los inputs pueden tener rasgos explotables (simplicidad, simetrías, variables interconectadas, etc.)
  • Fijar parametros (parametrized complexity)
  • Canjear exactitud por velocidad

EXP vs NEXP

**NEXP** = $\bigcup_{c \geq 0}$**NTIME**$(2^{n^c})$.

Ejercicio: encontrar la definición equivalente con certificados.

Teorema:

**EXP** ≠ **NEXP** implica **P** ≠ **NP**

Supongamos P=NP. Sea L$\in$NTIME$(2^{n^c})$, y M una MT para $L$.

Sea $L_{pad}={ x 0 1^{2^{|x|}^c} \mid x \in L }$. Mostramos que $L_{pad}\in$ NP:

Entonces si P=NP, $L_{pad}\in$P y existe $M’$ deterministica que decide $L_{pad}$.

Entonces $L\in$EXP: para decidir si $x \in$L, lo padeamos con $01^{2^{|x|^c}}$ y vemos si esto pertenece a $L_{pad}$ usando $M’$.

El problema de la factorización

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

Factorización:

Dado $n, m\in\mathbb{N}$ tal que $1 \leq m \leq 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\in\mathbb{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 $\setminus$ (P $\cup$ NPC)

  • isomorfirmo de grafos
  • problema de la autopista con peaje (turnpike problem): dadas $n(n-1)/2$ distancias entre pares de puntos, ¿les corresponde alguna configuración de $n$ puntos en una línea?

Teorema de Ladner

Si **P**≠**NP**, existe un lenguaje en **NP** $\setminus$ **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 P ≠ NP (≠ 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