Warum ist es wichtig zu beweisen, dass ein Problem NP-vollständig ist?

Stimmt es, dass es ein Forschungserfolg ist, ein Problem NP vollständig zu beweisen? Wenn ja warum?

Ali, gute Frage.

Angenommen, Sie möchten zeigen, dass ein Problem P rechenintensiv ist. Man könnte vermuten, dass P schwer ist, nur weil wir noch keine effizienten Algorithmen dafür haben. Aber das sind eher schwache Beweise, oder? Es könnte sein, dass wir einen schönen Blick auf P verpasst haben, der die Lösung sehr einfach macht. Um zu vermuten, dass P schwer ist, möchten wir mehr Beweise sammeln. Reduktionen bieten genau das! Wenn wir ein anderes natürliches Problem Q zu P reduzieren können, dann haben wir gezeigt, dass P mindestens so schwer ist wie Q. Aber Q könnte ein Problem aus einem ganz anderen Bereich der Mathematik sein, und die Menschen haben möglicherweise jahrzehntelang Mühe, Q auch zu lösen . Wir können also feststellen, dass wir keinen effizienten Algorithmus für Q gefunden haben, um zu beweisen, dass P hart ist. Wenn wir viele solcher Q 'haben

Genau das liefert die Theorie der NP-Vollständigkeit. Wenn Sie nachweisen, dass Ihr Problem NP-vollständig ist, haben Sie seine Härte an die Härte von Hunderten anderer Probleme gebunden, von denen jedes für verschiedene Gemeinschaften von großem Interesse ist. Moralisch gesehen können Sie also sicher sein, dass Ihr Problem tatsächlich schwierig ist.

Beweisen eines Problems NP-Complete ist ein Forschungserfolg, da Sie nicht mehr nach einer effizienten und genauen Lösung für das allgemeine Problem suchen müssen, das Sie gerade untersuchen. Es beweist, dass Ihr Problem zu einer Klasse von Problemen gehört, die so schwierig sind, dass niemand in der Lage war, einen effizienten und genauen Algorithmus für eines der Probleme zu finden, und eine solche Lösung für eines der Probleme würde eine Lösung für alle bedeuten Probleme.

Es ist in der Regel ein Sprungbrett, denn Ihr Problem ist immer noch da - Sie müssen einfach Ihre Anforderungen entspannen. Normalerweise versuchen die Leute herauszufinden, wie sie sich von "effizient", "genau" oder "allgemein" erholen können. Ineffizient und genau und allgemein ist der Versuch, immer bessere Konstanten im Exponenten für diese Algorithmen zu finden. Effizient-und-ungenau-und-allgemein ist das Studium von Approximationsalgorithmen. Effizient und genau, aber nicht allgemein ist die Untersuchung der Traktabilität fester Parameter und die Suche nach Unterklassen von Eingaben, für die effiziente Algorithmen gefunden werden können.

$NP-complete$

$NP-complete$, Sie haben Beweise für Ihre Vermutung und sollten über einen alternativen Ansatz nachdenken (z. B. das Problem zu ändern, damit es einfacher wird).

$NP-complete$

$NP-complete$

$P=NP$$3-SAT$

$NP-complete$$CLIQUE$

Wenn Sie ein Problem zusammenfassen und charakterisieren, können Sie gängige Techniken anwenden. Wenn Sie die Klasse studieren, auf die es sich bezieht, können Sie in einer abstrakten Ebene denken, ohne sich um die Besonderheiten dieses speziellen Problems zu kümmern, das in Mathematik und Naturwissenschaften im Allgemeinen üblich ist. Wenn Sie mit Klassen statt mit einzelnen Mitgliedern arbeiten, können Sie bekannte Techniken anwenden und außerdem Ihre Erkenntnisse auf eine größere Anzahl von Objekten anstatt nur auf eines anwenden.

Jedes Problem hat mehrere Verbindungen mit anderen Problemen. Hinzu kommen Zusammenhänge zwischen Problem- und Komplexitätsklassen.

Wenn wir daher ein Problem als NPC klassifizieren, erhalten wir normalerweise Einblick in andere Probleme sowie in Komplexitätsklassen.

Nehmen wir zum Beispiel das Problem des Graphisomorphismus (GI). In dem folgenden Papier:

Uwe Schöning, Graph Isomorphism is in the low hierarchy , Proceedings of the 4th Annual Symposium on Theoretical Aspects of Computer Science , 1987, 114–124; auch: Journal of Computer and System Sciences, vol. 37 (1988), 312–323.

es ist bewiesen, dass, wenn GI ∈ NPC ist, die Polynomhierarchie (PH) auf ihre zweite Ebene zusammenbricht; Dies wird ein großer Durchbruch in der Theorie der strukturellen Komplexität sein.

$p$$p$$p$$p$