¿Cuáles son las técnicas comunes para reducir problemas entre sí?

40

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 2L1L2L 1 L 1 L 2L2L1L1L2

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!

Rafael
fuente
Vea aquí algunas ideas sobre cómo encontrar socios adecuados e ideas para las reducciones.
Raphael

Respuestas:

18

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 1L1RL2RL1L2

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 RL2L1L2R

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

f(A,k)=(A,(1,,1),k,|A|)

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)vVWw

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

3SAT es un caso especial; con m el número de cláusulas en φ es suficiente.f(φ)=(φ,m)mφ

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

f(A)={(A,12aAa),aAamod2=0(A,1+aA|a|),else

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.kAA k(A,k)Akk

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 kGs,tGkstGk

Demuestre que el CAMINO MÁS LARGO es NP-duro.

HAMILTON-CYCLE es un conocido problema de NP completo y un caso especial de la VÍA MÁS LARGA; para el nodo arbitrario en suficiente. Observe en particular cómo reducir de HAMILTON-PATH requiere más trabajo.v Gf(G)=(G,v,v,n)vG

Rafael
fuente
2
Aquí hay un ejemplo llamado el problema del comprador viajero (TPP) que tiene muchos problemas difíciles como su caso especial.
Juho
Otro ejemplo de computabilidad es el problema especial de detención (que generalmente se demuestra directamente como indecidible), un caso especial del problema general de detención.
Raphael
¿KNAPSACK es realmente una reducción correcta de SUBSET-SUM? KNAPSACK solicita el valor y SUBSET-SUM solicita el valor exacto, ¿no? Por ejemplo, una instancia SUBSET-SUM sería una instancia 'no' (no puedo obtener exactamente 4 de solo un elemento con valor 5), pero su reducción de KNAPSACK reduciría eso a y , por lo que sería una instancia de 'sí' allí ... ¿O me estoy perdiendo algo? { 5 } , 4 { 5 } , { 1 } , 4 , 1 5 > 4>=v{5},4{5},{1},4,15>4
johnny
15

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

DOUBLE-SAT={φφ is a boolean formula with at least 2 satisfying assignments }

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

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.

Juho
fuente
6

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.

L

MKfML

K={MM(M) halts}

MfMfM

LK¯


  1. Aquí es donde entra en juego la numeración de Gödel: obtenemos la computabilidad de esta asignación (generalmente) de forma gratuita.
Rafael
fuente
-2

ABBA

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.

vzn
fuente
2
Me pregunto si notaste la nota al pie de la pregunta. Creo que las respuestas deberían ser más específicas y mostrar cómo se aplica un método específico. Esto parece bastante vago y general. Como mejora, ¿qué tal si muestra cómo se pueden construir y usar los gadgets?
Juho
2
ABBA
el powerpoint muestra dos ejemplos de dispositivos que se utilizan. Un ejemplo de un problema cercano: supongamos que uno tiene un problema relacionado con la teoría de números. Hay una sección de G&J relacionada con la teoría de números. etcétera En cuanto a otras clases de complejidad fuera de NP, hay muchas, pero las listas de problemas no son tan exhaustivas ni fáciles de obtener. en otras palabras, para reducir la pregunta original, ¿tal vez debería limitarse a reducciones completas de NP ...?
vzn
2
Recomiendo agregar toda la información a la respuesta, ya que los comentarios pueden eliminarse en cualquier momento. El enlace a las diapositivas también podría romperse mañana. A qué me refería con el problema cercano: ¿qué hago exactamente una vez que encuentro un problema similar (supongo que soy un principiante total)?
Juho