Dureté et sens des réductions

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

Par exemple: nous savons que la coloration 3 est difficile. Ensuite, nous réduisons la coloration 3 à la coloration 4. En combinant l'une des couleurs de la coloration 3, vous obtenez une coloration 4, l'ergo 4 est difficile.

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

Bonus q: Les réductions polynomiales doivent-elles pouvoir aller dans les deux sens?

Edit: si vous pouviez expliquer pourquoi il en est ainsi par un exemple, vous rendriez service à Internet. Je n'ai pu trouver cela expliqué de façon concrète nulle part.

Une réduction d'un problème à un autre problème est une transformation de toute instance de en une instance de , telle queB f a A f ( a ) $A$$B$$f$$a$$A$$f(a)$$B$

Si est une transformation préservant la complexité qui vous intéresse (par exemple est une transformation polynomiale si vous considérez la dureté ) alors l'existence d'un algorithme résolvant implique l'existence d'un algorithme résolvant : il suffit d'exécuter , puis .f N P A B B A f A$f$$f$$\mathsf{NP}$$\mathcal A_B$$B$$A$$f$$\mathcal A_B$

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

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

Vous pouvez construire une réduction correcte de à mais c'est un peu plus compliqué: pour tout graphe , soit le graphe étendu avec un autre noeud qui est lié avec un bord à tous les autres nœuds.3 C O L 4 C O L G f ( G ) G $f$$3\mathsf{COL}$$4\mathsf{COL}$$G$$f(G)$$G$$u$

• La transformation préserve la complexité (polynôme, ici);
• si est dans alors est dans : utilisez simplement la quatrième couleur pour ;3 C O L f ( G ) 4 C O L$G$$3\mathsf{COL}$$f(G)$$4\mathsf{COL}$$u$
• si est dans alors vous pouvez prouver que tous les nœuds sauf ont une couleur qui n'est pas celle de , donc est dans .4 C O L u u G 3 C O $f(G)$$4\mathsf{COL}$$u$$u$$G$$3\mathsf{COL}$

Cela prouve que est une réduction et que est plus difficile que . Vous pouvez prouver de la même manière que est plus dur que pour tout , la preuve intéressante étant que est plus dur que tout .4 C O L 3 C O L n C O L m C O L n ≥ m 3 C O L n C O $f$$4\mathsf{COL}$$3\mathsf{COL}$$n\mathsf{COL}$$m\mathsf{COL}$$n≥m$$3\mathsf{COL}$$n\mathsf{COL}$