Informatik: Was bedeutet die Komplexitätsklasse NP?
Ich habe zugegebenermaßen noch nie verstanden, was man unter einem NP-Problem versteht:
Es handelt sich hier ja (nach meinem Verständnis) um ein Entscheidungsproblem, welches mit einem nicht-deterministischen Algorithmus in polynomialer Zeit lösbar ist.
Ich habe leider mit dem Begriff “nicht-deterministisch” ein Problem: Was heißt es, beispielsweise wenn man sagt: DECIDE(x) – ein Entscheidungsproblem, ob x in einem Alphabet L liegt oder nicht – wäre unter Verwendung eines nicht deterministischen Algorithmus polynomial? Was wäre denn so ein nicht deterministischer Algorithmus bzw. was muss ich mir darunter vorstellen? Heißt es nur, dass ich in polynomialer Zeit prüfen kann, ob ein zufällig gewähltes x DECIDE(x) wahr oder falsch ist?
Aber damit löse ich ja nicht das Problem in polynomialer Zeit, denn mit einem Zufallsgenerator müsste ich ja beispielsweise für das Rucksack-Entscheidungsproblem (“kann ich den Wert W erreichen, ohne das Maximalgewicht zu überschreiten?)” müsste ich alle Kombinationen durchprobieren und selbst wenn jede einzelne Überprüfung in P liegt, habe ich exponenziell viele Möglichkeiten zu prüfen. Ich verstehe einfach nicht, was mit “nicht-deterministisch” gemeint ist.
Kann mir das jemand erklären?
(1 votes)
Loading...
“Nicht-Deterministisch” heißt grob gesagt, dass der Algorithmus sich bei identischer Eingabe unterschiedlich verhalten kann.
Beispiel: Wir wollen bei einem eingegebenen Graphen herausfinden, ob es eine 3-Clique gibt (i.e. ob er 3 Knoten hat, die alle untereinander verbunden sind).
Ein deterministischer Algorithmus könnte wie folgt aussehen:
Ein nicht-deterministischer Algorithmus könnte wie folgt aussehen:
Dieser Algorithmus prüft nur für eine einzige Teilmenge, ob sie eine 3-Clique ist. Er ist nicht-deterministisch, weil die zufällig ausgewählte Teilmenge bei verschiedenen Durchläufen mit derselben Eingabe unterschiedlich sein kann.
Du bemerkst sicher, dass der nicht-deterministische Algorithmus unter Umständen das falsche Ergebnis zurückliefert. Aber bei nicht-deterministischen Algorithmen verwenden wir andere Spielregeln: Die Antwort ist TRUE, wenn es einen möglichen Programmablauf gibt, der TRUE zurückliefert.
Wenn in meinem Graphen 100 Knoten liegen, unter denen sich genau 3 befinden, die eine 3-Clique bilden, dann muss unser nicht-deterministischer Algorithmus am Anfang ziemlich viel Glück haben, um ausgerechnet diese 3 Knoten zufällig auszuwählen. Nichtsdestotrotz ist das ein möglicher Programmablauf, weswegen die Antwort auf die Frage “Gibt es eine 3-Clique” durch unseren ND-Algorithmus bejaht wird.
Schauen wir uns die Laufzeiten an. Sagen wir, es gibt n Knoten im Graphen. Im Worst-Case muss der deterministische Algorithmus (n über 3) Teilmengen prüfen, bevor er zu einem Ergebnis kommt. Gehen wir davon aus, dass die einzelnen Prüfungen konstante Laufzeit haben, landen wir bei einer Laufzeit von O(n³).
Der nicht-deterministische Algorithmus hingegen braucht nur eine Teilmenge picken und prüfen und hat somit konstante Laufzeit O(1).
Da beides polynomiell ist, ist dies kein Beispiel für P vs NP, aber es demonstriert vielleicht, wie Determinismus/Nicht-Determinismus einen Unterschied machen könnte.
Warum führt man den abstrusen Begriff “nicht det. Alg.”, ein, wenn es so einen nicht geben kann? Dieser müsste ja alle Möglichkeiten gleichzeitig prüfen…
Weil er wohl für die Theorie nützlich ist. Es gibt wichtige Probleme, für deren Lösung man derzeit keinen polynomiellen herkömmlichen Algorithmus kennt.
Also nähert man sich von der anderen Seite: Wie könnten wir den Begriff “Algorithmus” erweitern, damit es eine polynomielle Lösung gibt?
Wenn wir so einen verallgemeinerten Begriff haben, können wir vllt eines von den folgenden Dingen bewerkstelligen:
Diese ND-Algorithmen sind eine solche Erweiterung. Tatsächlich kann man die auch in det-Algorithmen transformieren, aber alle bekannten Transformationen resultieren wieder in ineffizienten (nicht-polynomiellen) det-Algorithmen.
Wir brauchen weiterhin ND-Algorithmen, um überhaupt zu zeigen, dass Probleme in NP liegen, was eine Voraussetzung ist um NP-vollständig zu sein. Das ist insofern wichtig, da es für P=NP genügt zu zeigen, dass irgendein NP-vollständiges Problem von einem deterministischen Algorithmus in polynomieller Zeit gelöst werden kann.
NP bedeutet soviel wie das wenn du eine Lösung hast diese in polynomial zeit auf korrektheit prüfen kannst.
und was ist daran nun “nicht-deterministisch” ? wenn ich zufällig herausgegriffene Möglichkeiten vorgelegt bekomme und diese polynomial auf Korrektheit prüfen kann (bei Rucksackproblem trivial), habe ich ja nichts gewonnen, was die Lösung des Problems betrifft. Könnte ich so einen “nicht-deterministischen” Algorihmus implementieren, könnte ich ja das Rucksack-Entscheidungsproblem in polynomialer Zeit lösen – es kann sich also dabei nicht einfach daraum handeln, dass man zufällige Pack-Kombinationen zieht und diese auf Korrektheit prüft. Genau diesen Schritt habe ich noch nicht verstanden. Ein nicht-deterministischer Algorithmus muss also etwas “geisterhaftes” sein, das man nicht implementieren kann.
Es gibt 2 Möglichkeiten wie du es interpretieren kannst:
1. Die Maschine prüft alle Möglichkeiten gleichzeitig (also parallel), und sagt dass das Problem Lösbar ist, wenn mindestens eine Möglichkeit es löst.
2. Die Maschine hat ein Orakel, welches eine Zufällige Möglichkeit liefert, welches das Problem löst (bzw wenn es nicht lösbar ist, dann liefert es irgendeine Möglichkeit)
Ein Problem der Klasse P muss in Polynomieller Zeit gelöst werden, bei einem Problem der Klasse NP muss man nur in Polynomieller Zeit prüfen können, ob es eine Lösung ist.
NP ist die Menge von Problemen die in polynomialzeit durch eine NICHT deterministische Turing Maschine gelöst werden können. Der unterschied zu einer deterministischen TM ist das sie wenn sie in einem Zustand ist mehrer Auswahlmöglichkeiten hat was sie macht. Es handelt sich dabei nur um ein Theoretisches MODELL in der echten Welt gibt es keinen Computer der nicht determintisch arbeitet.
Wenn du ein Entscheidungproblem hast. Angenommen du hast einen Computer der das nicht determinitisch löst (was es nicht gibt). Du führst den Algortihmus mehrfach auf den gleichen Input aus und es kann trotzdem passieren, dass nicht immer das gleiche Ergebnis herauskommt (weil er immer anders vorgeht beim rechnen). Es wird ein Input mit „Ja“ beantwortet sobald eine der möglichen Berechnungen der nichtdeterministischen Tm dies tut.
Das Problem ist, dass ich den Begriff “NICHT deterministische Turing Maschine” im Gegensatz zur deterministischen nicht verstehe 😉 Ich weiß zwar, dass man NP so definiert, aber es hilt mit nicht weiter, da ich mir darunter nichts vorstellen kann.
PS: ich komme mir ziemlich doof vor, dass ich das nicht verstehe – sorry für die Frage…