algorithm - resueltos - qué es un problema np hard

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

Familiarícese con un subconjunto de NP Problemas completos
Demuestre la dureza NP: reduzca una instancia arbitraria de un problema NP completo a una instancia de su problema. Esta es la mayor parte de un pastel y donde la familiaridad con los problemas de NP Complete paga. La reducción será más o menos difícil según el problema NP Complete que elija.
Demuestre que su problema está en NP: diseñe un algoritmo que pueda verificar en tiempo polinomial si una instancia es una solución.

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 completo?

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

No es más fácil que el problema NP-complete, ya que se puede reducir a él en tiempo polinomial, lo que hace que el problema sea NP-Hard.

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

Para demostrar que un problema L es NP completo, necesitamos hacer los siguientes pasos:

Demuestre que su problema L pertenece a NP (es decir, si se le da una solución, puede verificarlo en tiempo polinomial)
Seleccione un problema conocido NP-complete L ''
Describe un algoritmo f que transforma L ''en L
Demuestre que su algoritmo es correcto (formalmente: x ∈ L ''si y solo si f (x) ∈ L)
Demuestre que algo f se ejecuta en tiempo polinomial

Para mostrar un problema es NP completa, debe:

Mostrar que está en NP

En otras palabras, dada cierta información C , puede crear un algoritmo de tiempo polinomial V que verificará para cada posible entrada X si X está 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 k tal que cada borde en G tiene al menos un vértice en el conjunto de cubiertas ?) Está en NP:

nuestra entrada X es un gráfico G y un número k (esto es de la definición del problema)
Considere que nuestra información C es "cualquier posible subconjunto de vértices en el gráfico G del tamaño k "
Entonces podemos escribir un algoritmo V que, dado G , k y C , devolverá si ese conjunto de vértices es una cobertura de vértice para G o no, en tiempo polinomial .

Luego, para cada gráfica G , si existe algún "posible subconjunto de vértices en G de tamaño k " que es una cobertura de vértice, entonces G está en NP .

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

Tenga en cuenta que el algoritmo V debería funcionar para cada G , para algunos C Para cada entrada debería existir información que podría 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 Duro

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

(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 booleanos, lo que hace que la expresión sea verdadera .

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

Es decir, dada alguna entrada X para SAT (o cualquier problema NP-completo que esté utilizando), cree una entrada Y para su problema, de modo que X esté en SAT si y solo si Y está en su problema. La función f : X -> Y debe ejecutarse en tiempo polinomial .

En el ejemplo anterior, la entrada Y sería el gráfico G y el tamaño de la cobertura del vértice k .

Para una prueba completa , debes probar ambos:

que X está en SAT => Y en tu problema
e Y en tu problema => X en SAT .

La respuesta de marcog tiene un enlace con varios otros problemas de NP-complete que podrías reducir a tu problema.

Nota al pie: en el paso 2 ( demuestre que es NP-hard ), reducirá otro problema NP-hard (no necesariamente NP-complete) al problema actual, ya que los problemas NP-complete son un subconjunto de problemas NP-hard (que son también en NP).

Primero, demuestras que yace en NP.

Luego encontrará otro problema que ya sabe que es NP completo y le mostrará cómo reduce polinómicamente el problema de NP Hard a su problema.