En la teoría de la computabilidad y la complejidad (y quizás en otros campos), las reducciones son ubicuas. Hay muchos tipos, pero el principio sigue siendo el mismo: demuestre que un problema es al menos tan difícil como otro problema al mapear instancias de a soluciones equivalentes en . Esencialmente, mostramos que cualquier solucionador para también puede resolver si permitimos que use la función de reducción como preprocesador.L 2L 1 L 1 L 2
He realizado mi parte de las reducciones a lo largo de los años, y algo me sigue molestando. Si bien cada nueva reducción requiere una construcción creativa (más o menos), la tarea puede parecer repetitiva. ¿Hay un grupo de métodos canónicos?
¿Cuáles son las técnicas, patrones y trucos que uno puede emplear regularmente para construir funciones de reducción?
Se supone que esto se convertirá en una pregunta de referencia . Por lo tanto, tenga cuidado de dar respuestas generales, presentadas didácticamente, que se ilustran con al menos un ejemplo pero que, sin embargo, cubren muchas situaciones. ¡Gracias!
Respuestas:
El caso especial
Suponemos que queremos mostrar con respecto a alguna noción de reducción . Si es un caso especial de , eso es bastante trivial: esencialmente podemos usar la función de identidad. La intuición detrás de esto es clara: el caso general es al menos tan difícil como el caso especial. R L 1L1≤RL2 R L1 L2
En "práctica", se nos da y estamos atrapados con el problema de elegir un buen compañero de reducción , es decir, encontrar un caso especial de que ha demostrado ser duro.L 1 L 2 RL2 L1 L2 R
Ejemplo simple
Supongamos que queremos mostrar que KNAPSACK es NP-hard. Afortunadamente, sabemos que SUBSET-SUM es NP-complete, y de hecho es un caso especial de KNAPSACK. La reducción
basta es la instancia de KNAPSACK que pregunta si podemos alcanzar al menos el valor v con los valores de los elementos en V para que los pesos correspondientes de W permanezcan por debajo de w en total. No necesitamos las restricciones de peso para simular SUBSET-SUM, por lo que solo las configuramos con valores tautológicos.( V, W, v , w ) v V W w
Problema de ejercicio simple
Considere el problema MAX-3SAT: dada una fórmula proposicional y un entero k , decida si existe una interpretación de φ que cumpla al menos k cláusulas. Demuestre que es NP-hard.φ k φ k
Ejemplo
Supongamos que estamos investigando el problema SUBSET-SUM y queremos demostrar que es NP-hard.
Tenemos suerte y sabemos que el problema de PARTICIÓN es NP-completo. Confirmamos que es un caso especial de SUBSET-SUM y formulamos
donde es el conjunto de entrada de PARTITION, y es una instancia de SUBSET-SUM que solicita un subconjunto de suma a . Aquí, tenemos que ocuparnos del caso de que no hay ajuste ; en ese caso, damos una instancia arbitraria inviable.kUNA A k( A , k ) UNA k k
Problema de ejercicio
Considere el problema de más larga PATH: dado un grafo dirigido , los nodos de y número entero , debe decidir si hay un camino simple de a en de longitud al menos .s , t G k s t G ksol s , t sol k s t sol k
Demuestre que el CAMINO MÁS LARGO es NP-duro.
fuente
Aprovechando un problema cercano conocido
Cuando se enfrenta a un problema que se siente difícil, a menudo es una buena idea tratar de buscar un problema similar que ya haya sido probado. O, tal vez pueda ver de inmediato que un problema es muy similar a un problema conocido.
Problema de ejemplo
Considera un problema
deseamos mostrar is -complete. Rápidamente notamos que está muy cerca de un problema que ya sabemos que es difícil, a saber, el problema de satisfacción (SAT) .NP
La membresía a es fácil de mostrar. El certificado son dos tareas. Claramente, se puede verificar en tiempo polinómico si las asignaciones satisfacen una fórmula.NP
SAT φ v ( v ∨ ¬ v ) φ v = ⊥ v = ⊤ φ φ vNP -dureza se deriva de una reducción de . Dada una fórmula , la modificamos introduciendo una nueva variable . Agregamos una nueva cláusula a la fórmula. Ahora, si es satisfactoria, será satisfactoria con y . Por lo tanto, tiene al menos 2 tareas satisfactorias. Por otro lado, si no es satisfactoria, definitivamente no será satisfactoria independientemente del valor de .SAT φ v (v∨¬v) φ v=⊥ v=⊤ φ φ v
De ello se deduce que es -complete, que es lo que queríamos mostrar.N PDOUBLE-SAT NP
Encontrar problemas cercanos
Reducir los problemas es una especie de arte, y a menudo se necesita experiencia e ingenio. Afortunadamente, ya se conocen muchos problemas difíciles . Las computadoras y la intratabilidad de Garey y Johnson: una guía para la teoría de la integridad de NP es clásica con su apéndice que enumera muchos problemas. Google Scholar también es un amigo.
fuente
En computabilidad, a menudo investigamos conjuntos de máquinas de Turing. Es decir, nuestros objetos son funciones y tenemos acceso a una numeración de Gödel . Eso es genial porque podemos hacer casi lo que queremos con la función de entrada, siempre y cuando sigamos siendo computables.
fuente
Una estrategia útil es trabajar a partir de grandes compilaciones de problemas de la clase de complejidad en cuestión y encontrar los "problemas más cercanos aparentes" al problema que se está estudiando. Una excelente referencia en este sentido es Computadoras e Intractabilidad, una guía de la teoría de la integridad de NP, Garey y Johnson organizada por diferentes tipos de problemas.
fuente