Härte und Reduktionsrichtungen

Nehmen wir an, wir wissen, dass Problem A schwierig ist, dann reduzieren wir A auf das unbekannte Problem B, um zu beweisen, dass B auch schwierig ist.

Als Beispiel: Wir wissen, dass 3-Farben schwer sind. Dann reduzieren wir 3-Farben auf 4-Farben. Durch das Zusammenführen einer der Farben in der 3-Färbung erhalten Sie eine 4-Färbung, ergo 4-Färbung ist schwer.

So geht's. Aber warum ist dies ein Beweis dafür, dass 4-Farben schwer sind? Können Sie die Lösung für das 4-Farben-Problem verwenden, um das 3-Farben-Problem zu lösen? Wenn das so ist, wie? Wenn nicht, warum ist es ein gültiger Beweis?

Bonus q: Müssen die Polynomreduktionen in beide Richtungen gehen können?

Bearbeiten: Wenn Sie anhand eines Beispiels erklären könnten, warum dies so ist, würden Sie dem Internet einen Gefallen tun. Ich konnte das nirgendwo konkret erklären.

Eine Reduktion von einem Problem zu einem anderen Problem ist eine Transformation einer beliebigen Instanz von in eine Instanz von , so dassB f a A f ( a ) $A$$B$$f$$a$$A$$f(a)$$B$

Wenn eine Transformation ist, die die Komplexität bewahrt, an der Sie interessiert sind (z. B. ist eine Polynomtransformation, wenn Sie -Härte berücksichtigen) , impliziert die Existenz eines Algorithmus , der löst , die Existenz eines Algorithmus, der löst : Es reicht aus, und dann .f N P A B B A f A$f$$f$$\mathsf{NP}$$\mathcal A_B$$B$$A$$f$$\mathcal A_B$

Daher ist die Existenz einer solchen Reduktion von zu bedeutet , dass nicht einfacher als . Eine Reduzierung ist nicht erforderlich.B B $A$$B$$B$$A$

Zum Beispiel zum Färben von Diagrammen. Sie können 3-Farben auf 4-Farben reduzieren, jedoch nicht sofort. Wenn Sie einen Graphen und wählen, haben Sie aber Sie haben nicht natürlich. Die Schlussfolgerung ist , dass die Äquivalenz nicht eingehalten wird , so ist nicht eine Reduktion.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$

Sie können eine korrekte Reduktion von auf , dies ist jedoch etwas komplizierter: Für jeden Graphen sei der Graph um einen anderen Knoten ist mit einer Kante zu jedem anderen Knoten verbunden.3 C O L 4 C O L G f ( G ) G $f$$3\mathsf{COL}$$4\mathsf{COL}$$G$$f(G)$$G$$u$

• Die Transformation ist komplexitätserhaltend (Polynom hier);
• Wenn in dann ist in : benutze einfach die vierte Farbe für ;3 C O L f ( G ) 4 C O L$G$$3\mathsf{COL}$$f(G)$$4\mathsf{COL}$$u$
• Wenn in ist, können Sie beweisen, dass alle Knoten außer eine Farbe haben, die nicht , daher ist in .4 C O L u u G 3 C O $f(G)$$4\mathsf{COL}$$u$$u$$G$$3\mathsf{COL}$

Das beweist, dass eine Reduktion ist und dass schwieriger ist als . Sie können auf die gleiche Weise beweisen, dass für jedes schwieriger ist als , wobei der interessante Beweis dafür ist, dass schwieriger ist als jedes .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}$