P, NP, NP-Vollständigkeit

[Kirby.exe]

Alsoo ich wir behandeln derzeit die oben genannten Themen in Datenstrukturen & Algorithmen 2 und ehrlich gesagt verstehe ich hier nur Bahnhof xD

Was ich bis jetzt verstanden habe ist:

Ein Problem liegt in P genau dann, wenn ein Algorithmus existiert der dieses Problem in Polynomialzeit löst.

Ein Problem liegt in NP genau dann, wenn ein Algorithmus existiert welcher mithilfe eines Zertifikats und einer Instanz diese Instanz in Polynomialzeit verifizieren kann.

Wie genau NP-Vollständigkeit funktioniert verstehe ich nicht so ganz. Außerdem wüsste ich jetzt nicht richtig wie ich zeige, dass etwas in P oder NP liegt...Soll ich mir dazu einfach einen Algorithmus überlegen und diesen dann erläutern und müsste man diesbezüglich noch mehr beweisen xD

BTW: Sollte jemand einen guten Buchtipp für dieses Thema haben wäre das sehr hilfreich

 

[LimDul]

P = Problem kann deterministisch in Polynomialzeit gelöst werden
NP = Problem kann nicht-deterministisch in Polynomialzeit gelöst werden (N steht für nicht deterministisch, nicht für nicht). Anders kann man das auch definieren, wenn ich einen Lösungsvorschlag habe, kann ich deterministisch in Polynomialzeit prüfen, ob diese Lösung korrekt ist. Klassisches Beispiel ist da 3-SAT: https://de.wikipedia.org/wiki/3-SAT. Wenn ich für jede der Variablen einen Wert von TRUE oder FALSE habe kann ich in Linearzeit prüfen, ob der Ausdruck wahr ist. Es gibt aber bisher noch keinen Algorithmus, der in Polynomialzeit eine Belegung der Variablen findet, so dass der Ausdruck wahr ist. (Man braucht bisher exponentielle Zeit)

Es gilt P ist eine Teilmenge von NP. Also alles, was in P liegt, liegt offensichtlich auch in NP.

NP-vollständig kann man jetzt wie folgt definieren:
* Ein Problem ist NP-vollständig, wenn es in NP liegt und es mindestens so schwer wie jedes andere Problem in NP ist (Diesen Teil nennt man auch NP-Hart).

Dazu nutzt man den Mechanismus Probleme auf andere zu transformieren. Ich hab Beispielsweise ein Problem X und möchte wissen ist das NP-vollständig. Dazu brauche ich erst mal ein anderes NP-vollständiges Problem (Klassiker hier wieder: 3-SAT). Dann macht man folgendes:
* Ich forme das 3-SAT Problem so lange um, bis ich das Problem X habe
* Die Umformung muss folgenden Randbedingungen genügen:
** Sie muss in Polynomialzeit erfolgen
** Wenn ich eine Lösung für mein Problem X habe, habe ich automatisch auch die Lösung für das ursprüngliche 3-SAT Problem.

Das heißt, mein Problem ist mindestens so schwer wie 3-SAT, denn wenn ich mein Problem in Polynomialzeit lösen kann, kann ich auch 3-SAT in Polynomialzeit lösen. (=NP-Hart). Da ich aber gleichzeitig weiß, dass es in NP ist (also auch nicht schwerer als das maximal schwere Problem in NP), ist es NP-vollständig.

Für die Beweise ob etwas in P oder NP liegt:

* Suche einen Algorithmus, der für eine gegebene Eingabe überprüft, ob die Eingabe das Problem löst. Wenn du diesen Algorithmus in Polynomuialzeit duchführen kannst => Problem liegt in NP
* Wenn du zusätzlich diese Eingabe auch in Polynomialzeit ermitteln kannst => Problem liegt auch in P.

 

[Kirby.exe]

Vielen Dank für die ausführliche Erklärung