La dureté et les directions des réductions

Question

Disons que nous savons ce problème A est difficile, nous réduisons A au problème inconnu B de prouver B est également difficile.

À titre d'exemple: nous savons 3-coloration est difficile. Ensuite, nous réduisons 3 coloration à 4-coloration. En amalgamant l'une des couleurs dans le 3-coloration vous avez un 4-coloration, ergo 4-coloration est difficile.

C'est le comment. Mais pourquoi est-ce une preuve que 4-coloration est difficile? Est-ce que vous pouvez utiliser la solution au problème 4-coloration pour résoudre le problème 3-coloration? Si c'est le cas, comment? Sinon, pourquoi est-il une preuve valable?

Bonus q: Faut-il que des réductions polynomiales pouvoir aller dans les deux sens

Edit: si vous seriez en mesure d'expliquer pourquoi il en est ainsi par exemple que vous faites Internet une faveur. Je ne pouvais pas trouver ce qui explique dans une partout façon concrète.

Answer 1

Une réduction d'un problème $ A $ à un autre problème $ B $ est un $ de transformation f $ d'aucun cas $ a $ de $ A $ dans une instance $ f (a) $ de $ B $, de telle sorte que

$$ \ qquad \ qquad x?A ~~ ~~ ? f (x) ?B \ qquad \ qquad (E) $$

Si $ f $ est une transformation en préservant la complexité qui vous intéresse (par exemple $ f $ est une transformation polynomiale si vous considérez $ \ mathsf {NP} $ - dureté), alors l'existence d'un algorithme $ \ mathcal A_B $ résolution $ B $ implique l'existence d'un algorithme de résolution de $ A $: il suffit de courir $ f $, alors $ \ mathcal A_B $

.

D'où l'existence de la réduction d'un de $ A $ à $ B $ que moyen de $ B $ n'est pas plus facile que $ A $. Il est pas nécessaire d'avoir une réduction dans l'autre sens.

Par exemple, pour le graphique coloration. Vous pouvez réduire de 3 à 4 coloration-coloration, mais pas de la manière immédiate. Si vous prenez un graphique $ G $ et que vous choisissez $ f (G) = G $, alors vous aurez que x?3 $ \ mathsf {COL} $ $ $ $ ? f (x) ?4 \ mathsf {COL} $ mais vous n'avez pas $ f (x) ?4 \ mathsf {COL} $ $ $ $ ? x?3 \ mathsf {COL} $ bien sûr. La conclusion est que l'$ d'équivalence (E) $ est pas respectée, alors $ f $ est pas une réduction.

Vous pouvez construire une $ de réduction correcte f $ de 3 $ \ mathsf {COL} $ à 4 $ \ mathsf {COL} $, mais il est un peu plus compliqué: pour tout graphe $ G $, soit $ f (G) $ le graphe $ G $ étendu avec un autre noeud u $ $ qui est lié avec un bord à chaque autre noeud.

• La transformation est la complexité de préservation (polynomiale, ici);
• si $ G $ est 3 $ \ mathsf {COL} $, alors $ f (G) $ est 4 $ \ mathsf {COL} $: il suffit d'utiliser la quatrième couleur pour $ u $;
• si $ f (G) $ est 4 $ \ mathsf {COL} alors $ vous pouvez prouver que tous les nœuds sauf $ u $ ont une couleur qui n'est pas $ u $ s ', d'où G $ est en 3 $ \ mathsf {COL} $.

Cela prouve que $ f $ est une réduction et que 4 $ \ mathsf {COL} $ est plus difficile que 3 $ \ mathsf {COL} $. Vous pouvez prouver la même façon que $ n \ mathsf {COL} $ est plus difficile que $ m \ mathsf {COL} $ pour tout n=m de $ $, la preuve intéressante étant du fait que 3 $ \ mathsf {COL} $ est plus fort que tout $ n \ mathsf {COL} $.