¿Cómo demostrar que un problema es NP completo?

108

Tengo un problema con la programación. Necesito demostrar que el problema es NP completo. ¿Cuáles pueden ser los métodos para demostrar que NP está completo?

algorithm thetna
fuente
Lea "Reducibilidad entre problemas combinatorios" de Karp.
Paul Hankin

Respuestas:

146

Para mostrar que un problema es NP completo, debe:

Demuestre que está en NP

En otras palabras, dada alguna información C, puede crear un algoritmo de tiempo polinomial Vque verificará para cada entrada posible Xsi Xestá en su dominio o no.

Ejemplo

Demuestre que el problema de las cubiertas de vértices (es decir, para algún gráfico G, ¿tiene un conjunto de cubiertas de vértices de tamaño ktal que cada borde en Gtenga al menos un vértice en el conjunto de cubiertas ?) Está en NP:

  • nuestra entrada Xes un gráfico Gy un número k(esto es de la definición del problema)

  • Considere nuestra información Ccomo "cualquier posible subconjunto de vértices en el gráfico Gde tamaño k".

  • Luego podemos escribir un algoritmo Vque, dado G, ky C, devolverá si ese conjunto de vértices es una cobertura de vértice para Go no, en tiempo polinomial .

Luego, para cada gráfico G, si existe algún "posible subconjunto de vértices Gde tamaño k" que sea una cobertura de vértices, entonces Gestá en NP.

Tenga en cuenta que no es necesario encontrar Cen tiempo polinomial. Si pudiéramos, el problema estaría en `P.

Tenga en cuenta que el algoritmo Vdebería funcionar para todos G , para algunos C. Para cada entrada debe existir información que pueda ayudarnos a verificar si la entrada está en el dominio del problema o no. Es decir, no debe haber una entrada donde la información no exista.

Demuestra que es NP Hard

Esto implica obtener un problema NP-completo conocido como SAT , el conjunto de expresiones booleanas en la forma:

(A o B o C) y (D o E o F) y ...

donde la expresión es satisfactoria , es decir, existe alguna configuración para estos valores booleanos, lo que hace que la expresión sea verdadera .

Luego, reduzca el problema NP-completo a su problema en tiempo polinomial .

Es decir, dada alguna entrada Xpara SAT(o cualquier problema NP-completo que esté usando), cree alguna entrada Ypara su problema, de modo que Xesté en SAT si y solo si Yestá en su problema. La función f : X -> Ydebe ejecutarse en tiempo polinomial .

En el ejemplo anterior, la entrada Ysería el gráfico Gy el tamaño de la cubierta del vértice k.

Para una prueba completa , tendrías que probar ambos:

  • eso Xestá en SAT=> Yen tu problema

  • y Yen su problema => Xen SAT.

La respuesta de marcog tiene un vínculo con varios otros problemas NP-complete que podría reducir a su problema.

Nota a pie de página: En el paso 2 ( Demuestre que es NP-difícil ), será suficiente reducir otro problema NP-difícil (no necesariamente NP-completo) al problema actual, ya que los problemas NP-completo son un subconjunto de los problemas NP-difíciles (que son también en NP).

Laila Agaev
fuente
7
Me pregunto si faltan datos o hay un razonamiento circular detrás de esto. Quiero decir, ¿cómo 'probar' que un problema está en NP sin referirlo a otro problema que 'ya está en NP'? Es como decir "está hecho de hierro porque se sabe que su parte es hierro", eso no es una prueba de hierro.
Hernán Eche
6
Por lo que recuerdo, existe un teorema llamado teorema de Cook-Levin que establece que SAT es NP-completo. Esa prueba es un poco más complicada de lo que describí anteriormente y no creo que pueda explicarlo con mis propias palabras.
Laila Agaev
4
Para ser más precisos, el teorema de Cook-Levin establece que SAT es NP-completo: cualquier problema en NP puede reducirse en tiempo polinomial mediante una máquina de Turing determinista al problema de determinar si una fórmula booleana es satisfactoria (SAT). Esa es la pieza que faltaba por la que preguntabas. Si busca el teorema en Wikipedia, hay una prueba, y puede hacer referencia al teorema en su demostración. Dicho esto, reducir el SAT a un problema dado es la forma en que me enseñaron a demostrar que el NP es completo.
Laila Agaev
Entonces mi pregunta termina siendo si SAT podría resolverse en polinomio, es decir, el problema P = NP .. Gracias por su respuesta.
Hernán Eche
¿Podría explicar por qué no podemos reducir un problema NP-difícil al problema que queremos, en el segundo paso? ¿Tiene que ser un problema NP-completo?
MLT
23

Necesita reducir un problema NP-Complete al problema que tiene. Si la reducción se puede hacer en tiempo polinomial, entonces ha probado que su problema es NP-completo, si el problema ya está en NP, porque:

No es más fácil que el problema NP-completo, ya que se puede reducir en tiempo polinomial lo que hace que el problema NP-Difícil.

Consulte el final de http://www.ics.uci.edu/~eppstein/161/960312.html para obtener más información.

Moinudin
fuente
2
+1 alguien que explica comprensiblemente. en lugar de decir un montón de referencias a palabras clave que apenas entiendo.
ColacX
22
La primera oración es de atrás hacia adelante: necesita reducir el problema NP-completo conocido a su propio problema. Esto muestra que su problema es al menos tan difícil como el problema NP-completo conocido. La parte (b) también es incorrecta: si ha encontrado la reducción, entonces ya sabe que su problema es NP-difícil; la única pregunta es si está en NP en absoluto (algunos problemas, como el problema de detención, no lo están). Si es NP-duro y en NP, entonces es NP-completo (es decir, "NP-completo" es más específico que "NP-duro").
j_random_hacker
1
Yo no diría que a) conduce a una contradicción, ya que no sabemos que P! = NP.
Chiel ten Brinke
8

Para demostrar que un problema L es NP-completo, debemos seguir los siguientes pasos:

  1. Demuestra que tu problema L pertenece a NP (es decir, que dada una solución puedes verificarlo en tiempo polinomial)
  2. Seleccione un problema NP-completo conocido L '
  3. Describe un algoritmo f que transforma L 'en L
  4. Demuestre que su algoritmo es correcto (formalmente: x ∈ L 'si y solo si f (x) ∈ L)
  5. Demuestre que algo f se ejecuta en tiempo polinomial
Albert s
fuente
7

Primero, demuestra que se encuentra en NP en absoluto.

Luego, encuentra otro problema que ya sabe que es NP completo y muestra cómo reduce polinomialmente el problema NP Difícil a su problema.

Lagerbaer
fuente
No. Debe demostrar que puede reducir de un problema NP completo a su problema NP para demostrar que NP está completo Y demostrar que está en NP en absoluto. NP hard no entra en esto, a menos que no puedas probar que está en NP.
mrmemio29
6
  1. Familiarizarse con un subconjunto de problemas NP Complete
  2. Demuestre la dureza NP: Reduzca una instancia arbitraria de un problema NP completo a una instancia de su problema. Este es el pedazo más grande de un pastel y donde vale la pena familiarizarse con los problemas NP Complete. La reducción será más o menos difícil según el problema NP Complete que elija.
  3. Demuestre que su problema está en NP: diseñe un algoritmo que pueda verificar en tiempo polinomial si una instancia es una solución.
UmNyobe
fuente