Wie wird die Reduktion verwendet, um die Härte durch Widerspruch nachzuweisen?

Question

Ich bin kein Student, der einen computational complexity Kurs absolviert, nur an dem Thema interessiert. Ich kam in diesem Abschnitt:

Angenommen, wir haben ein Problem, dass wir bewiesen haben, ist schwer zu lösen, und wir haben ein ähnliches neues Problem. Wir könnten vermuten, dass es auch schwer zu lösen ist. Wir argumentieren durch Widerspruch: angenommen, das neue Problem ist einfach zu lösen. Wenn wir dann zeigen können, dass jede Instanz des alten Problems leicht gelöst werden kann, indem man es in Instanzen des neuen Problems transformiert und diese löst, haben wir einen Widerspruch. Diese stellt fest, dass das neue Problem auch schwer ist.

Quelle: Wikipedia

ich meinen Kopf nicht scheinen kann umschlingen, was das bedeutet. Kannst du diesen Prozess im Sinne des Laien erklären (so viel wie möglich), wie ein Beweis des Widerspruchs als solcher funktionieren würde?

Ist der Widerspruch, dass wir das alte Problem kennen, schwierig, aber wir sind in der Lage, es auf ein neues Problem zu reduzieren und zu lösen, dass das Alte mindestens so einfach wie neu ist? Diese ganze Idee ist verwirrend für mich. Kann mir das jemand erklären, der keinen soliden Hintergrund in der computational complexity theory hat?

Answer 1

Sagen wir, dass wir für eine Tatsache wissen, dass Aufgabe A eine schwere Aufgabe ist. Jetzt sagen wir, dass wir Aufgabe B erhalten und gefragt werden, ob es schwer ist oder nicht. Tue so, als ob wir einen Weg finden, um Task A effizient in ein paar Teile aufzuteilen, und jeder Teil entpuppt sich als Task B. Das heißt, Task A kann leicht ausgeführt werden, indem eine kleine Anzahl von Task Bs ausgeführt wird. Kann Aufgabe B jetzt einfach sein? Wenn es so wäre, könnte ich auch Aufgabe A leicht machen. Das wäre allerdings ein Widerspruch, denn ich weiß, dass Aufgabe A hart ist. Deshalb muss Aufgabe B auch hart sein.

Es ist wichtig zu beachten, dass alle Fälle von Aufgabe A auf B reduziert werden müssen, damit dies gilt. Wenn nur einige Fälle dies tun, dann könnte B einfach sein, aber im Allgemeinen keine einfache Lösung für A bereitstellen, daher gibt es nicht notwendigerweise einen Widerspruch. Auch wenn es sehr viel kostet, A zu B zu reduzieren (dh die Reduktion selbst ist hart), dann gibt es nicht notwendigerweise einen Widerspruch, wenn B einfach ist.