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.
fuente
Respuestas:
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 queA B f a A f(a) B
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 .f f NP AB B A f AB
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.A B B A
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 L ⇒ f ( x ) ∈ 4 C O L pero no tienes f ( x ) ∈ 4 C O L ⇒ x ∈ 3 C O L, por supuesto. La conclusión es que la equivalencia (G f(G)=G x∈3COL ⇒ f(x)∈4COL f(x)∈4COL ⇒ x∈3COL no se respeta, entonces f noesuna reducción.(E) 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.f 3COL 4COL G f(G) G u
Eso prueba quef 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 .4COL 3COL nCOL mCOL n≥m 3COL nCOL
fuente