WikiDer > NP-komplett

NP-Vollständigkeit ist ein Konzept aus dem Komplexitätstheorie. Es ist eine Beschreibung der Einsicht aus dem 70er Jahre dass es einen gewissen Zusammenhang zwischen der Komplexität vieler Probleme gibt, die in der Mathematik und Informatik als "schwierig" angesehen.

Formal ist ein Problem genau dann NP-vollständig (manchmal auch NP-vollständig genannt), wenn

• das problem bis zum KomplexitätsklasseNP gehört.
• jedes andere Problem in NP in polynomieller Zeit kann auf dieses Problem reduziert werden.

Die Basis

Das Komplexitätstheorie ist der Zweig der Mathematik und Informatik, der untersucht, ob Probleme lösbar sind oder nicht und wenn sie lösbar sind, wie schwer sie zu lösen sind. Das Hauptwerkzeug in dieser Forschung ist a Konzeptionelles Modell der Berechnung, genannt die Turing Maschine. Dieses Modell beschreibt auf sehr niedrigem Niveau und auf sehr mechanische Weise, wie eine Berechnung durchgeführt wird. Eine solche Beschreibung besteht eigentlich aus einer Zusammenfassung aller Schritte, die befolgt werden müssen, um aus einer Problemstellung zu einer Lösung zu kommen. Anhand dieses Modells zur Beschreibung von Berechnungen lässt sich feststellen, ob ein gegebenes Problem überhaupt lösbar ist. Ein Problem gilt als lösbar, wenn es eine Turingmaschine geben kann, die das Problem löst beschlossen.

Wenn ein Problem sicher lösbar ist, stellt sich die Frage, wie schwer das Problem zu lösen ist. Um dies zu beantworten, schauen wir uns die Komplexitätsgrad von dem Problem.

Löslichkeitsklassen

Das Sammlung der Turing-entscheidbaren (d. h. der lösbaren) Probleme enthält zwei Klassen: die Klasse P der "einfachen" zu lösenden Probleme und die Klasse NP der "einfachen" zu überprüfenden Probleme. Es ist eine offene Frage, ob die Klassen zusammenfallen oder nicht.

Die Klasse P

sehen P (Komplexitätsklasse) für den Hauptartikel zu diesem Thema.

Im Allgemeinen werden solche (lösbaren) Probleme als "einfach" bezeichnet, die a Polynom Zeitkomplexität haben. Was bedeutet:

${displaystyle P={Mitte A={mathcal {O}}(f(x))Keil f(x)=Summe _{k=0}^{N}c_{k}x^{k}}}$

Das X in obiger Formel steht für die Größe der Probleminstanz, dh die Größe der Eingabe in die Turingmaschine.

Mit anderen Worten: Die Klasse P enthält die Probleme, die mit einem Algorithmus gelöst werden können, der in Polynomzeit ausgeführt werden (die Zeitdauer des Algorithmus ist begrenzt durch a Polynom).

Die Klasse NP

sehen NP (Komplexitätsklasse) für den Hauptartikel zu diesem Thema.

Es wird oft angenommen, dass NP für „nicht polynomiell“ steht und dass die Klasse NP aus den Problemen besteht, die nicht in polynomialer Zeit gelöst werden können, aber das ist falsch. NP steht für 'nichtdeterministisches Polynom' und enthält die Probleme, die in polynomieller Zeit auf einer nichtdeterministischen Turingmaschine gelöst werden können.

EIN nichtdeterministische Turingmaschine ist eine imaginäre Maschine, die mehrere Varianten einer Berechnung gleichzeitig untersuchen kann. Die Maschine wählt automatisch die Variante, in der eine Lösung gefunden wird, und verwirft die Varianten, die nicht zu einer Lösung führen. Es ist jedoch nicht bekannt, ob eine solche Maschine tatsächlich existieren kann.

Es ist bekannt, dass die Klasse P eine Teilmenge der Klasse ist NP (${displaystyle Psubseteq {NP}}$Schließlich können P-Probleme in polynomieller Zeit und damit per Definition auch in nichtdeterministischer polynomialer Zeit gelöst werden. Mit anderen Worten, wenn Sie ein Problem in polynomieller Zeit lösen können, können Sie es auch in polynomieller Zeit verifizieren.

Es gibt jedoch auch Probleme in NP, von denen viele zeitgenössische Mathematiker glauben, dass sie nicht deterministisch gelöst werden können.Polynomzeit sind lösbar (und damit "schwierig"). Beispiele hierfür sind die NP-vollständigen Probleme.

Die Probleme in NP zeichnen sich alle durch eine eigene Eigenschaft aus: Sie sind polynomiell überprüfbar. Dies bedeutet, dass wir diese Probleme möglicherweise nicht in polynomieller Zeit lösen können, aber wenn wir eine Lösung für ein Problem vermuten, können wir in polynomieller Zeit überprüfen, ob diese Lösung richtig ist.

Mit anderen Worten enthält die Klasse NP alle Probleme, für die ein Algorithmus existiert, der bei gegebenem Lösungsvorschlag in polynomieller Zeit prüfen kann, ob der Lösungsvorschlag richtig ist.

Reduktion und NP-Vollständigkeit

Die Ermäßigung

In dem Komplexitätstheorie Es war seit einiger Zeit bekannt, dass man Eigenschaften bekannter Probleme auf neue Probleme übertragen kann, wenn man beweisen kann, dass man das neue Problem durch das alte Problem ausdrücken kann; so heißt es reduzieren eines Problems. Ein typisches Beispiel hierfür ist das Problem der Suche nach a Eulerweg, was ausgedrückt werden kann durch das Finden von a Euler-Zyklus. Oder finden Sie Hamilton-Zyklus durch die Probleme mit dem Handelsreisenden.

Zu Beginn des 1970er kam zwei Mathematiker -- Stephen Cook und Leonid Levin -- zu einer besonderen Einsicht. Innerhalb der Klasse NP existiert ein System von Problemen, die durch Reduktion in polynomieller Zeit miteinander verbunden sind (d. h. die Beschreibung eines Problems in einem anderen kann in polynomieller Zeit erfolgen). Tatsächlich bezieht sich dieses Problemsystem auf alle Probleme in NP durch Reduktion der Polynomialzeit.

Innerhalb von NP existiert eine Teilmenge von NP. Jedes Problem in NP kann durch all diese speziellen Probleme gelöst werden (so ist es auch möglich, diese Probleme aufeinander zu reduzieren). Cook und Levin nannten diese spezielle Teilmenge von NP die Menge NPC (aus dem Englischen NP-Complete): die Menge von NP-vollständige Probleme.

NP-Vollständigkeit

NP-vollständige Probleme sind Probleme, die in der Komplexitätsklasse NP liegen und für die außerdem gilt, dass jedes Problem in NP in polynomieller Zeit auf sie reduziert werden kann. Sie können daher auch aufeinander reduziert werden. Somit bilden die NP-vollständigen Probleme a vollständige Zählung der gegenseitigen Reduzierbarkeit. Die Einführung der NP-Vollständigkeit in Mathematik und Informatik war ein wichtiges Hilfsmittel bei der Klassifikation von Problemen. Es könnte auch der Schlüssel zur Lösung des obigen Rätsels sein. Schließlich ist jedes Problem in NP auf jedes NP-vollständige Problem reduzierbar. Wenn also jemals ein NP-vollständiges Problem gefunden wird, das polynomiell lösbar ist, folgt automatisch, dass alle NP-Probleme polynomiell lösbar sind, mit anderen Worten: ${Anzeigestil P=NP}$.

Es Erfüllungsproblem ist das erste Problem, für das NP-Vollständigkeit demonstriert wurde.

Nachweis der NP-Vollständigkeit

Um zu beweisen, dass ein gegebenes Problem A NP-vollständig ist, werden formal zwei Dinge benötigt:

1. Ein Beweis, dass A zu NP . gehört
2. Ein Beweis, dass jedes Problem in NP in polynomieller Zeit auf A reduziert wird

Der erste Teil ist oft (aber nicht immer!) einfach, indem er einen Algorithmus bereitstellt, der Lösungen für A in polynomieller Zeit verifiziert. Die Herausforderung liegt normalerweise im zweiten Stück, dem Beweis, dass jedes Problem in NP auf A reduziert wird. Probleme, die die zweite Anforderung erfüllen, werden auch als bezeichnet NP-hart erwähnt. Es ist jedoch auch möglich, dass ein Problem die zweite Anforderung erfüllt, aber nicht die erste, zum Beispiel die Wahl des besten Zugs in einer Schachpartie, dies ist „schwieriger“ als NP. Dieser Beweis wird jedoch normalerweise zu einem Beweis vereinfacht, der einige Probleme in NPC auf A reduziert. Dies ist eine Erweiterung des "NPC-Baums" und das reicht als Beweis. Angenommen, B ist ein Problem in NPC. Dann reduziert sich jedes Problem in NP (einschließlich A) auf B. Wenn B auch auf A reduziert wird, reduziert sich jedes Problem in NP über B auf A. Den Anfang des "NPC-Baumes" bildet das Problem SAT (Erfüllbarkeit). Cook und Levin demonstrierten unabhängig voneinander die NP-Vollständigkeit dieses Problems mit einem außergewöhnlichen Beweis (in dem sie offensichtlich nicht die Bequemlichkeit hatten, ein weiteres NP-vollständiges Problem zu reduzieren, denn ihr Problem war das erste, das das NP-vollständige Problem löste. Vollständigkeit war bekannt).