Dureza y direcciones de reducciones

9

Digamos que sabemos que el problema A es difícil, luego reducimos A al problema desconocido B para probar que B también es difícil.

Como ejemplo: sabemos que 3 colores es difícil. Luego reducimos 3 colores a 4 colores. Al combinar uno de los colores en 3 colores, tiene 4 colores, ergo 4 colores es difícil.

Así es como. Pero, ¿por qué es esto una prueba de que 4 colores es difícil? ¿Es posible usar la solución al problema de 4 colores para resolver el problema de 3 colores? ¿Si es así, cómo? Si no, ¿por qué es una prueba válida?

Bonus q: ¿Deben ser posibles las reducciones polinómicas en ambos sentidos?

Editar: si pudiera explicar por qué esto es así con un ejemplo, le haría un favor a Internet. No pude encontrar esto explicado de manera concreta en ninguna parte.

El gato no divertido
fuente
Si está lidiando con dos problemas de NP completo, entonces sí, debe haber reducciones polinómicas que vayan en ambos sentidos. En muchos casos, las reducciones de A a B y de B a A pueden ser muy diferentes entre sí.
Joe
Si los problemas no están en la misma clase de complejidad, entonces puede que no haya una reducción en ambos sentidos.
Joe

Respuestas:

7

Una reducción de un problema a otro problema B es una transformación f de cualquier instancia a de A en una instancia f ( a ) de B , de modo queAsiFunaUNAF(una)si

XUNA    F(X)si(mi)

Si es una transformación que preserva la complejidad que le interesa (por ejemplo, f es una transformación polinomial si considera N D- dureza), entonces la existencia de un algoritmo A B que resuelve B implica la existencia de un algoritmo que resuelve A : es suficiente para ejecutar f , entonces A B .FFnortePAGSUNAsisiUNAFUNAsi

Por lo tanto la existencia de reducción tal de a B medios que B no es más fácil que A . No es necesario tener una reducción al revés.UNAsisiUNA

Por ejemplo, para colorear gráficos. Puede reducir 3 colores a 4 colores, pero no de manera inmediata. Si tomas una gráfica y eliges f ( G ) = G, entonces tendrás ese x 3 C O Lf ( x ) 4 C O L pero no tienes f ( x ) 4 C O Lx 3 C O L, por supuesto. La conclusión es que la equivalencia (solF(sol)=solX3COL F(X)4 4COLF(X)4 4COL X3COL no se respeta, entonces f noesuna reducción.(mi)F

Puede construir una reducción correcta de 3 C O L a 4 C O L pero es un poco más complicado: para cualquier gráfico G , deje que f ( G ) sea ​​el gráfico G extendido con otro nodo u que está vinculado con un borde a cualquier otro nodo.F3COL4 4COLsolF(sol)soltu

  • La transformación preserva la complejidad (polinomio, aquí);
  • si está en 3 C O L, entonces f ( G ) está en 4 C O L : simplemente use el cuarto color para usted ;sol3COLF(sol)4 4COLtu
  • si está en 4 C O L entonces se puede demostrar que todos los nodos excepto u tienen un color que no es u 's, por lo tanto, G está en 3 C O L .F(sol)4COLuuG3COL

Eso prueba que f es una reducción y que es más duro que 3 C O L . Puede probar la misma manera que n C O L es más difícil que m C O L para cualquier n m , la prueba interesante es el hecho de que 3 C O L es más duro que cualquier n C O L .4COL3COLnCOLmCOLnm3COLnCOL

jmad
fuente
¿Por qué tal reducción significa que B no es más fácil que A? UV por esfuerzo, pero demasiado abstracto para mi pequeño cerebro.
The Unfun Cat
¿Es que la respuesta será la misma para B que para A después de haber reducido A a B? Creo que lo entendí: si la instancia original tiene tres colores, entonces la instancia transformada tendrá cuatro colores, así que si la respuesta es "sí, tiene cuatro colores", la respuesta también es "sí, tiene un tres colores "? Pero, ¿no es posible que la instancia transformada B tenga cuatro colores sin que A tenga tres colores? Me imagino que es más fácil colorear un gráfico con cuatro colores ...
The Unfun Cat
@TheUnfunCat (actualizado con un ejemplo de 3 y 4 colores)
jmad