% Clase 4: Clase NP.

Clase NP

¿Problemas que no están en P?

• la clase P es la clase de todos los lenguajes decidibles en tiempo polinomial
• pero hay muchos lenguajes decibibles que no parecen tener algoritmos de decisión en tiempo polinomial

Problema Subset Sum

• dado un conjunto de enteros, ¿existe algún subconjunto cuya suma sea exactamente cero?
• ejemplo: { −7, −3, −2, 5, 8}
• la respuesta es SI: { −3, −2, 5} suma cero
• algoritmo exponencial: verificar todos posibles subconjuntos
• tiempo de ejecución: $O(2^N N)$ ($2^N$ subconjuntos, para cada uno sumar $N$ elementos)
• no se conoce algoritmo polinomial

Observación

• dados dos conjuntos de enteros x y s
• es fácil (= polinomial) chequear si s es subconjunto de x
• es fácil (= polinomial) chequear si s suma cero
• si se cumple lo anterior, el tamaño de s es chico (= polinomial) en función del tamaño de x
• o sea el problema “suma de subconjuntos” es fácilmente chequeable cuando se provee solución

Definición clase NP

• Un lenguaje $L \subseteq {0,1}^$ pertenece a 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 del lenguaje $L$, y $u$ un certificado de la instancia $x$.

Acerca de NP

• Intuición: cuando un lenguaje L está en NP, si $x$ es una instancia del lenguaje L, entonces $u$ es una solución a $x$ que es corta y se puede chequear rápidamente
• el nombre viene de “P definido con MT nodeterministas”, una definición alternativa de NP que no vamos a usar acá
• P $\subseteq$ NP

Mostrar que un lenguaje es NP

• La definición de NP involucra tiempos y tamaños polinomiales
• Entonces, como en el caso de P, no hace falta definir máquinas de Turing
• Con algoritmos en pseudocódigo alcanza.

Lenguaje 3SAT

El lenguaje 3SAT

• problema de 3SAT:
  • variables Booleanas $x1, x2, \ldots, xn$
  • conjunto de cláusulas, que relacionan como máximo 3 variables:

x2 or x5 or not(x6)
not(x2) or x4
not(x4) or not(x5) or x6

• problema: ¿hay alguna forma de asignar valores “verdadero” o “falso” a las variables para que todas las cláusulas se evaluen a “verdadero”?
• 3SAT está en NP, ¿por qué?

P y NP

• P $\subseteq$ NP $\subseteq$ EXPTIME
• no se sabe si P ≠ NP, ni si NP ≠ EXPTIME.
• en P están los problemas fáciles
• en NP están los problemas difíciles pero que tienen soluciones facilmente chequeables
• NP representa los problemas de búsqueda con soluciones cortas

Ejercicios

Problema de la autopista con peaje

1. Dadas n(n − 1) / 2 distancias entre pares de puntos, ¿les corresponde alguna configuración de n puntos en una línea?
   • Definir un lenguaje que corresponde a ese problema.
   • Mostrar que ese lenguaje está en NP.

Conjuntos independientes

1. El lenguaje INDSET contiene todos los pares $(G,k)$ tales que $G$ es un grafo, y tiene un subgrafo de $k$ nodos que no tienen ninguna arista entre ellos.

   Mostrar que ese lenguaje está en NP.