Ein sehr komplexes Problem der Reduktion

Question

Ich habe viel über Reduktion gelernt, aber ich habe ein großes Problem damit: Ich nehme dies von CLRS:

" ... indem wir die Lösung von Problem A auf die Lösung von Problem B "reduzieren", nutzen wir die "Leichtigkeit" von B, um die "Leichtigkeit" von A zu beweisen."

Ich entnehme dies dem Buch "Computational Complexity von Christos H. Papadimitriou":

" ... Problem A ist mindestens so schwer wie Problem B, wenn B auf A reduziert."

Ich bin mit diesen beiden Begriffen durcheinander gekommen: Wenn wir Leichtigkeit verwenden, sagen wir, dass das Problem X auf das Problem Y reduziert wird, und wenn wir einen Polynomialzeit-Algorithmus für Y haben und der Reduktionsprozess in Polynomialzeit durchgeführt wird, dann ist das Problem X in Polynomialzeit lösbar und X ist einfacher als Y oder zumindest nicht schwieriger als Y.

Aber wenn wir Härte verwenden, sagen wir, Problem X reduziert auf Problem Y und Y ist einfacher als X oder zumindest nicht schwieriger als X.

Ich bin wirklich verwirrt, bitte helfen Sie mir. Besonderen Dank.

Answer 1

Ich glaube, Sie haben übersehen, dass es im ersten Zitat heißt: "A auf B reduzieren", und im zweiten Zitat: "B auf A reduzieren".

Wenn X auf Y reduziert wird, d. h. Y zur Lösung von X verwendet werden kann, dann ist X nicht schwieriger als Y. Das liegt daran, dass die Reduktion der Polynomkomplexität als "frei" angesehen wird, so dass wir durch die Reduktion von X auf Y einen Weg gefunden haben, X zu lösen, indem wir alle Lösungen für Y verwenden.

Wenn also im ersten Zitat A auf B reduziert wird und B einfach ist, bedeutet das, dass A einfach ist (streng genommen ist es nicht schwieriger).

Das zweite Zitat verwendet den logischen Kontrapositiv: Wenn B auf A reduziert und B schwer ist, dann muss A schwer sein (streng genommen ist es nicht einfacher). Der Beweis: Wenn A einfach wäre, dann wäre auch B einfach (wie oben, aber A und B sind vertauscht). B ist nicht leicht, also ist A nicht leicht.

Ihre Aussage "Wir sagen, dass Problem X auf Problem Y reduziert werden kann und Y einfacher als X ist oder zumindest nicht schwieriger als X" ist falsch. Es ist möglich, X auf Y zu reduzieren (d. h. wir können Y zur Lösung von X verwenden), auch wenn Y in Wirklichkeit es Wir könnten also die Addition (X) auf einen Spezialfall eines NP-schweren Problems (Y) reduzieren, indem wir ein Schema definieren, um in polynomieller Zeit eine Instanz des NP-schweren Problems zu konstruieren, dessen Lösung die Summe unserer beiden Eingabezahlen ist. Das bedeutet nicht, dass die Addition NP-schwer ist, sondern nur, dass wir uns die Sache unnötig schwer gemacht haben. Es ist unklug, die verwenden. diese Reduktion, um die Addition durchzuführen, denn es gibt bessere Möglichkeiten, die Addition durchzuführen. Nun, unter der Annahme, dass P!=NP ist, ist das besser.

Answer 2

Stellen Sie sich die Reduktion als Reduktion des Beweises dafür vor, dass das Problem in einer bestimmten Klasse liegt, und nicht als Reduktion des Problems selbst. Die Beziehung hat mehr mit Logik als mit Komplexität zu tun.

Answer 3

Die Theorie ist einfach die folgende.

Sie haben einen Algorithmus zur Lösung von Problem A, von dem Sie wissen, dass er in polynominaler Zeit gelöst werden kann.

Wenn es möglich ist, Problem B in eine Notation umzuwandeln, die von Problem A gelöst werden kann, und das Ergebnis dann in polynominaler Zeit zurück in die Notation für Problem B umzuwandeln, dann wird auch die Lösung von Problem B in polynominaler Zeit erfolgen - da die Gesamtzeit nur die Addition von zwei polynominalen Werten ist - also nicht schwieriger.