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

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?

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 $\mathsf{3SAT}$$\mathsf{3Color}$$\mathsf{3Partition}$ 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$\mathsf{HamiltonianCycle}$$\mathsf{HamiltonianPath}$$\mathsf{Clique}$$\mathsf{IndependentSet}$ 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.$\mathsf{PlanarCircuitSAT}$$\mathsf{PlanarTSP}$$\mathsf{3SAT}$$\mathsf{CircuitSAT}$

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 $\mathsf{Minesweeper}$ o $\mathsf{Tetris}$ u $\mathsf{OneCheckersMove}$ o $\mathsf{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).$\mathsf{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.$\mathsf{3Color}$

• Para transformar una instancia de , necesitará un dispositivo para cada entrada, para cada cable y para cada puerta en el circuito de entrada.$\mathsf{PlanarCircuitSat}$

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 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.