Reducciones completadas de NP

Question

He leído que "cada problema en NP se puede reducir a cada problema de NP-Complete".

Mi pregunta es sobre la elección de la palabra "reducir". Si tuviera que "reducir" un problema polinómico en NP a un problema exponencial en NP, simplemente me siento extraño por usar la palabra "reducir" porque siento que he aumentado el problema, no lo he reducido. Entonces, ¿por qué usamos la palabra reduce?

Además, ¿por qué escribimos "Reducir A a B" como $ a le_ {p} b $? Parece al revés.

Answer 1

Una reducción de A a B muestra que A no es "más difícil" que B en cierto sentido. Lo llamamos una reducción porque reduce el problema de resolver un problema de resolver B. Este es un uso de la palabra "reducir" que es más matemático y menos sobre "tamaño"; Puede pensar que es decir, hemos reducido la cantidad de trabajo que el mundo tiene que hacer, porque a pesar de que no hemos resuelto A o B con la reducción, hemos hecho para que una solución a B también automáticamente también sea automáticamente Sea una solución a A.

Donde A era un problema para el que no teníamos ninguna solución eficiente, y donde ya tenemos una solución eficiente para B, esto da como resultado que A se vuelva "más pequeño" en cierto sentido. Por ejemplo, digamos que ya se nos ocurrió una solución exponencial a A, y B es un problema completo de NP. Anteriormente, lo mejor que sabíamos era que A era un problema exponencial. Después de que alguien se le ocurre la reducción A -> B, ahora sabemos que en realidad es un problema de NP.

Sí, puede usar un argumento de reducción para demostrar que un problema ya conocido es "no es más difícil" que un problema difícil. De hecho, puede usar una reducción de tiempo polinómico de NINGÚN problema en p a NINGÚN Otro problema en absoluto (que tiene al menos una instancia de "sí" y al menos una instancia de "no"), porque puede "resolver" el problema P en la reducción, pero simplemente codifica la respuesta como una instancia de otro problema. Sí, esto no tiene sentido. Pero no es "incorrecto" o inconsistente.

El problema que está teniendo es puramente en la analogía que está utilizando, a saber, que una reducción es una "forma de hacer un problema más pequeño". Esa es una metáfora razonable para uno de los habituales objetivos de pruebas de reducción, que es mostrar que un problema es "más fácil" de lo que se sospecha anteriormente al encontrar una manera de reducirlo a otro problema que ya se sabe que es "más fácil".

Pero eso no te ayuda con el otro uso extremadamente común de los argumentos de reducción, que es mostrar que un problema C es imposible resolver, al encontrar una reducción de Otro problema D que ya se sabe que es imposible. Aquí el argumento de reducción no es "hacer D más pequeño", está mostrando que C es "grande".

Trate de pensar en un argumento de reducción de A -> B como una forma de demostrar que A no es "más difícil" que B. Cuando lo piensas de esa manera, no es sorprendente que a menudo puedas reducir los problemas fáciles de los duros. ; ¡Ya sabíamos que eran más fáciles! Esta cuenta también explica fácilmente las pruebas de incomputabilidad por reducción; Si el problema de detención no es más difícil que X, entonces X no puede ser solucionable.

Answer 2

Principalmente del comentario de Vor:

Se puede tomar $ A LE_PB $ significa que el problema $ A $ es al menos tan fácil como $ B $ (o menos difícil). El subíndice $ _p $ significa tiempo polinomial e indica que "fácil" es un término relativo aquí, y la dificultad de los problemas reales debe considerar el tiempo polinomial La reducción como intrascendente (como cuando se resuelve $ B $ requiere tiempo superpolinomial).