Fachrat Informatik - Forum

Naja, es gibt da schon einen Unterschied: bei P bastelst du einen Algorithmus, der dir eine Lösung zu einem Problem zurückgibt, also quasi die Antwort auf das Problem.
Bei NP kennst du schon eine Antwort und du überprüfst nur noch, ob sie zu dem Problem passt. Wenn dies in polyn-zeit funktioniert, ist das Problem in NP. Das Zertifikat ist dabei "der Weg durch den Entscheidungsbaum", also quasi das, was du zwingend zum Überprüfen brauchst.
Du kennst quasi eine Antwort und überprüfst sie nur noch, wärend du bei P noch auf die Antwort kommen musst.

Hey,

ich glaub wenn man sich das ein wenig genauer anschaut sollte das recht klar werden.

Ein P Algorithmus entscheidet ob ein Wort zu einer Sprache gehört. Dies muss von einer deterministischen Turingmaschine in polynomieller Laufzeit gemacht werden können. Irgendwann gabs mal in THI son beweis, dass man Turingmaschinen auch als Programme mit FOR/WHILE schleifen ausdrücken kann. Gib also einfach nen Algorithmus an, der in polynomieller Zeit das Problem entscheidet.. Also z.B. mit schritte zählen und dann die Komplexitätsklasse bestimmen, wobei da meist reicht wenn man sagen kann "das ist polynomiell, das mit dem auch, also ist es insgesamt polynomiell". Aber sonst ist ein O(n^k) immer schön in P (k=konstante).

NP Sprachen werden von nicht deterministischen Touringmaschinen entschieden. Da gibts natürlich immer den schönen Weg über das Zertifikat, wenn man in polynomieller Zeit sagen kann "jap das ist in der Sprache", dann ist die Länge der Berechnungswege polynomiell beschränkt. Verzweigen/Raten darf ja ne Touringmaschine und alle Pfade gleichzeitig abarbeiten. Manchmal ists aber auch einfacher direkt die nichtdeterministische Touring Maschine anzugeben. Z.B. könnte nen Beweis wie folgt aussehen


1. Zertifikat
Setz die Variablenbelegung in die Formel ein und da es nicht mehr Logische Operatoren als Eingabezeichen gibt kann man den Wahrheitswert der Formel in Polynomieller Zeit berechnen (zumindest linear, kann auch schneller gehen, aber wen interessierts hier )

2. NTM für SAT



Da ist halt das raten nicht deterministisch und das auswerten in P, also ists ne NP Maschine. Vielleicht wird hier auch klar. Variante 1. ist ein P-Algorithmus der entscheidet ob die Belegung zur Formel passt, daraus folgt dass das Problem dessen Zertifikat in 1 berechnet wird in NP liegt (das könnte auch ein P-Problem sein!).
Variante 2. ist eine NTM und die entscheidet ob es irgendeine Belegung gibt, für die die Formel wahr ist, das ist deutlich schwerer als das Problem in Variante 1 und benötigt den Rate schritt.

PS: Warum geht kein Latex in Source Code ?

Zu den beiden angesprochenen Wegen kann man auch für die nichtdeterministische Variante im Hinterkopf haben, dass man das Zertifikat in der Regel einfach rät und dann anschließend den Verifikationsalgorithmus laufen lässt. Genauso wie es im SAT-Beispiel von Helicase gemacht worden ist. Möchte man das allgemein betrachten sieht das dann im Prinzip so aus:
1. Mitgliedschaft in NP über Zertifikat zeigen:

Eingabe: ursprüngliche Instanz, Zertifikat
1. Überprüfe deterministisch, ob Zertifikat eine gültige Lösung für die gegebene Instanz ist.
2. Falls ja, gebe "Ja" zurück. Sonst gebe "Nein" zurück.

2. Mitgliedschaft in NP über NTM zeigen:

Eingabe: ursprüngliche Instanz
1. Konstruiere nichtdeterministische (dh. rate) eine mögliche Lösung.
2. Überprüfe deterministisch, ob diese Lösung eine gültige für die gegebene Instanz ist.
3. Falls ja, gebe "Ja" zurück. Sonst gebe "Nein" zurück.

[quote Suey]Beispiel: Ü4, A1 - zu zeigen ist: Connected gehört zur Klasse P. Dann folgt ein Algorithmus, der einen Graphen übergeben bekommt und den dann durchläuft und true/false zurückgibt, ob es ein Connected-Graph ist oder nicht. [/quote]
Der Unterschied zum NP Algorithmus ist hier jedoch, dass man konkret am Graphen Markierungen setzt, was alles erreichbar ist. Man konstruiert also schrittweise eine Begründung weshalb der Graph (nicht) connected ist. Am Ende kann man sagen, dass der Graph (nicht) connected ist, weil man jeden Knoten erreichen kann bzw. eine bestimmte Anzahl von Knoten nicht erreichen kann. Bei NP-Algorithmen wird man, wie oben schon erklärt, vor "vollendete Tatsachen" gestellt und muss nur noch sagen, ob's stimmt oder nicht.

Diesen Unterschied zwischen P und NP kann man auch durch ein 2-Spieler-Spiel verdeutlichen.
1. Mitgliedschaft in P: Hier gibst Du Deinem Kommilitonen die Instanz und fragst ihn, ob dies eine positive oder negative Instanz ist. Im nächsten Zug sagt Dir Dein Kommilitone sofort "positiv" oder "negativ" und kann es in Polynomialzeit begründen.
2. Mitgliedschaft in NP: Hier gibst Du Deinem Kommilitonen die Instanz und fragst ihn, ob dies eine positive oder negative Instanz ist. Im nächsten Zug gibt Dir Dein Kommilitone eine Begründung (oder Zertifikat, oder Lösung) dafür, dass es dazu gehören soll. Du musst ihn in Polynomialzeit überprüfen können, ob er lügt oder nicht.