¿Cómo construyo reducciones entre problemas para probar que un problema es NP completo?

27

Estoy tomando un curso de complejidad y tengo problemas para encontrar reducciones entre los problemas de la APN. ¿Cómo puedo encontrar reducciones entre problemas? ¿Hay algún truco general que pueda usar? ¿Cómo debo abordar un problema que me pide que demuestre que un problema es NPC?

Anónimo
fuente
44
Lamento decepcionarte, no creo que haya un método que lo resuelva todo. Al igual que muchos problemas en la vida, cada uno es único. Con suerte, con el tiempo, obtendrá el presentimiento correcto de cómo resolver cada uno.
Ran G.
1
¿Hay algunas pautas útiles sobre cómo abordar estos problemas? Estoy completamente perdido cuando veo una pregunta que me pide que demuestre que es NPC. ¿Cómo debo acercarme a ellos?
Anónimo

Respuestas:

45

No hay bala mágica; Las pruebas de dureza NP son duras. Sin embargo, existe un marco general para todas esas pruebas. Muchos estudiantes que luchan con las pruebas de dureza NP están confundidos acerca de lo que se supone que deben hacer, lo que obviamente hace que sea imposible descubrir cómo hacerlo. Entonces, esto es lo que debe hacer para probar un problema NP-hard.

Primero, a menos que solo esté haciendo la tarea, debe decidir qué problema NP-difícil reducir a su problema . Esto es en gran medida una cuestión de "olor". Si el número 3 aparece en alguna parte del enunciado del problema, intente reducirlo de o 3 C o l o r o 3 P a r t i t i o n . (Sí, lo digo en serio.) Si su problema consiste en encontrar una subsecuencia óptima o permutación o la ruta, intente reducir de H un m i l t o n i una3SUNAT3doolor3PAGSunartyotyoonorte o H un m i l t o n i un n P un t h . Si su problema solicita el subconjunto más pequeño con una determinada propiedad, intente C l i q u e ; si solicita el subconjunto más grande con una determinada propiedad, intente I n d e p e n d e n t S e t . Si su problema implica hacer algo en el avión, intente PHunametroyoltonorteyounanortedoydolmiHunametroyoltonorteyounanortePAGSunathCliqueIndependentSet o P l a n un r T S P . Y así. Si su problema no "huele" a nada, 3 S A T o C i r c u i t S A T es probablemente su mejor opción.PlanarCircuitSATPlanarTSP3SATCircuitSAT

Obviamente, ya debes saber precisión cómo se definen todos estos problemas , y cuanto más simple sea el problema del que se reduce, mejor. Entonces, a pesar de que el resultado podría parecer al final, no recomiendo reducir de Minesweeper o Tetris u OneCheckersMove o SuperMarioBros .

En segundo lugar, la reducción real. Para reducir el problema X (el que sabe que es NP-hard) al problema Y (el que está tratando de probar es NP-hard, debe describir un algoritmo que transforma una instancia arbitraria de X en una instancia legal de Y El algoritmo de reducción necesita hacer algo específico con cada "característica" de la instancia X, la porción de la salida para cada "característica" generalmente se llama un gadget .

Pero, ¿qué es una característica? Eso depende del problema X. Por ejemplo:

  • Para transformar una instancia de , necesitará un gadget para cada variable y para cada cláusula en la fórmula de entrada. Cada gadget variable debe tener dos "estados" que corresponden a "verdadero" y "falso". Cada gadget de cláusula también debe tener múltiples "estados", cada uno de los cuales de alguna manera obliga a que al menos uno de los literales en esa cláusula sea verdadero. (Los estados no son parte de la salida del algoritmo de reducción).3SAT

  • Para transformar una instancia de , necesitará un gadget para cada vértice y cada borde del gráfico de entrada, y otro gadget para definir los tres colores.3Color

  • Para transformar una instancia de , necesitará un dispositivo para cada entrada, para cada cable y para cada puerta en el circuito de entrada.PAGSlunanorteunardoyordotuyotSunat

La forma real del gadget problema depende de Y, el que usted está reduciendo a . Por ejemplo, si está reduciendo a un problema con los gráficos, sus gadgets serán pequeños subgrafos; ver el artículo de Wikipedia. Si está reduciendo a un problema sobre la programación, cada gadget será un conjunto de trabajos que se programarán. Si se está reduciendo a un problema sobre Mario , cada dispositivo será un conjunto de bloques y ladrillos y Koopas.

Esto puede ser confuso si ambos problemas involucran el mismo tipo de objeto. Por ejemplo, si tanto X como Y son problemas con las gráficas, su algoritmo va a transformar una gráfica (una instancia de X) en una gráfica diferente (una instancia de Y). Elija su notación sabiamente, para no confundir estos dos gráficos. También recomiendo usar varios colores de tinta.

Finalmente, su algoritmo de reducción debe satisfacer tres propiedades:

  • Se ejecuta en tiempo polinomial. (Esto suele ser fácil).

  • Si su algoritmo de reducción recibe una instancia positiva de X como entrada, produce una instancia positiva de Y como salida.

  • Si su algoritmo de reducción produce una instancia positiva de Y como salida, se le debe haber dado una instancia positiva de X como entrada.

Hay una sutileza importante aquí. Su algoritmo de reducción solo funciona en una dirección, de instancias de X a instancias de Y, pero probar que el algoritmo es correcto requiere razonar sobre la transformación en ambas direcciones. También debe recordar que su algoritmo de reducción no puede determinar si una instancia determinada de X es positiva o negativa, ¡eso requeriría resolver un problema NP-difícil en el tiempo polinómico!

Eso es lo que . El cómo solo viene con la práctica.

JeffE
fuente
55
3SUNAT3SUNATpagstrtumiFunalsmi
1
Con respecto a "Si su algoritmo de reducción produce una instancia positiva de Y como salida, debe haber recibido una instancia positiva de X como entrada": aunque parecería más intuitivo escribir esta condición como "Si su algoritmo de reducción recibe una instancia negativa de X como entrada, produce una instancia negativa de Y como salida ", observe que estas dos condiciones son equivalentes , y cómo JeffE lo ha escrito generalmente hace que la construcción de la prueba sea mucho más fácil, ya que en cada caso" tiene algo "(ya sea instancia positiva de X, o la instancia positiva de Y) para trabajar.
j_random_hacker
11

JeffE describe la estrategia más común: conozca muchos problemas de NP completo, encuentre uno que se adapte muy bien y haga la reducción fácil .

Otra estrategia válida es usar siempre 3SAT (o cualquier otro problema). Esto puede hacer que algunas reducciones sean más complejas, pero lo bueno es que tienes mucha experiencia en expresar la saciedad en otros tipos de problemas. Por lo tanto, ahorra el tiempo de encontrar un buen socio de reducción (incluidos los callejones sin salida) y espera que su experiencia le permita hacer la reducción rápidamente, incluso si es más difícil.

Este enfoque también tiene cierta meta belleza: (3) SAT es uno de los pocos problemas para los cuales se ha demostrado (casi) directamente la completitud NP. Por lo tanto, confiar solo en esa prueba mantiene su "árbol de prueba" plano, evitando largas cadenas de reducciones.

Rafael
fuente
3
Probar directamente que el problema de Detención limitada es NP-completo cuando el límite se da en unario no es demasiado difícil, y es una forma fácil de demostrar que existe algún problema de NP completo, aunque el problema en sí es bastante inútil de reducir.
Alex ten Brink
3
No estoy seguro acerca de la afirmación de que es el único problema que se ha demostrado que es NP-completo directamente. De hecho, si lo interpreta en sentido estricto, definitivamente es falso. El artículo de Cook de 1971 habla sobre TAUT, no SAT (usa las reducciones de Cook, no las reducciones de Karp) (es una observación fácil de que la prueba también prueba que SAT es NP-completo bajo las reducciones de Karp).
Kaveh
@Kaveh ¿Eh? La tautología es Co-Np completa y, por lo tanto, no se sabe que esté en NP (-completo). Sin embargo, no leí el periódico de Cook.
Albert Hendriks
1
@ Albert, bueno, entonces deberías leerlo. Con las reducciones de Cook no se puede distinguir entre NP y coNP.
Kaveh