DAA - P & NP Klasse
In der Informatik werden viele Probleme gelöst, bei denen das Ziel darin besteht, einige Werte zu maximieren oder zu minimieren, während wir bei anderen Problemen versuchen, herauszufinden, ob es eine Lösung gibt oder nicht. Daher können die Probleme wie folgt kategorisiert werden:
Optimierungsproblem
Optimierungsprobleme sind solche, bei denen das Ziel darin besteht, einige Werte zu maximieren oder zu minimieren. Zum Beispiel,
Ermitteln der Mindestanzahl von Farben, die zum Färben eines bestimmten Diagramms erforderlich sind.
Finden des kürzesten Pfades zwischen zwei Eckpunkten in einem Diagramm.
Entscheidungsproblem
Es gibt viele Probleme, für die die Antwort Ja oder Nein lautet. Diese Arten von Problemen werden als bezeichnet decision problems. Zum Beispiel,
Gibt an, ob ein bestimmtes Diagramm nur mit 4 Farben eingefärbt werden kann.
Das Finden des Hamilton-Zyklus in einem Diagramm ist kein Entscheidungsproblem, während das Überprüfen eines Diagramms ein Hamilton-Problem ist oder nicht.
Was ist Sprache?
Jedes Entscheidungsproblem kann nur zwei Antworten haben, ja oder nein. Daher kann ein Entscheidungsproblem zu einer Sprache gehören, wenn es für eine bestimmte Eingabe die Antwort "Ja" liefert. Eine Sprache ist die Gesamtheit der Eingaben, für die die Antwort Ja lautet. Die meisten der in den vorherigen Kapiteln beschriebenen Algorithmen sindpolynomial time algorithms.
Für die Eingabegröße n, wenn die Worst-Case-Zeitkomplexität eines Algorithmus ist O(nk), wo k ist eine Konstante, der Algorithmus ist ein Polynomzeitalgorithmus.
Algorithmen wie Matrixkettenmultiplikation, kürzester Pfad aus einer Quelle, kürzester Pfad aller Paare, minimaler Spanning Tree usw. werden in Polynomzeit ausgeführt. Es gibt jedoch viele Probleme, wie z. B. reisende Verkäufer, optimale Diagrammfärbung, Hamilton-Zyklen, Finden des längsten Pfades in einem Diagramm und Erfüllen einer Booleschen Formel, für die keine Polynomzeitalgorithmen bekannt sind. Diese Probleme gehören zu einer interessanten Klasse von Problemen, die alsNP-Complete Probleme, deren Status unbekannt ist.
In diesem Zusammenhang können wir die Probleme wie folgt kategorisieren:
P-Klasse
Die Klasse P besteht aus den Problemen, die in Polynomzeit lösbar sind, dh diese Probleme können rechtzeitig gelöst werden O(nk) im schlimmsten Fall wo k ist konstant.
Diese Probleme werden genannt tractable, während andere genannt werden intractable or superpolynomial.
Formal ist ein Algorithmus ein Polynomzeitalgorithmus, wenn ein Polynom existiert p(n) so dass der Algorithmus jede Instanz der Größe lösen kann n in einer Zeit O(p(n)).
Problem erforderlich Ω(n50) Zeit zu lösen sind für große im Wesentlichen unlösbar n. Der bekannteste Polynomzeitalgorithmus läuft zeitlich abO(nk) für ziemlich niedrigen Wert von k.
Die Vorteile bei der Betrachtung der Klasse der Polynom-Zeit-Algorithmen sind, dass alle vernünftig sind deterministic single processor model of computation kann mit höchstens einem Polynom slow-d aufeinander simuliert werden
NP-Klasse
Die Klasse NP besteht aus den Problemen, die in der Polynomzeit überprüfbar sind. NP ist die Klasse von Entscheidungsproblemen, für die es einfach ist, die Richtigkeit einer behaupteten Antwort mit Hilfe einiger zusätzlicher Informationen zu überprüfen. Daher fragen wir nicht nach einer Möglichkeit, eine Lösung zu finden, sondern nur, um zu überprüfen, ob eine angebliche Lösung wirklich korrekt ist.
Jedes Problem in dieser Klasse kann in exponentieller Zeit durch umfassende Suche gelöst werden.
P gegen NP
Jedes Entscheidungsproblem, das durch einen deterministischen Polynomzeitalgorithmus lösbar ist, ist auch durch einen nichtdeterministischen Polynomzeitalgorithmus lösbar.
Alle Probleme in P können mit Polynomzeitalgorithmen gelöst werden, während alle Probleme in NP - P unlösbar sind.
Es ist nicht bekannt, ob P = NP. In NP sind jedoch viele Probleme mit der Eigenschaft bekannt, dass, wenn sie zu P gehören, bewiesen werden kann, dass P = NP ist.
Wenn P ≠ NPgibt es Probleme in NP, die weder in P noch in NP-Complete sind.
Das Problem gehört zur Klasse Pwenn es einfach ist, eine Lösung für das Problem zu finden. Das Problem gehört dazuNP, wenn es einfach ist, eine Lösung zu überprüfen, deren Suche möglicherweise sehr mühsam war.