P und NP - Für Laien erklärt
Montag, 9. August 2010 | Autor: Nico
Heute ist ein Beweis für P≠NP aufgetaucht und Informatiker in aller Welt sind irgendwie aufgeregt. Aber was bedeuten P und NP?
Einleitung
Ist ein Problem in P oder NP? - das ist eine Frage von deren Antwort abhängen kann, ob die Berechnung der exakten Lösung ein paar Stunden dauert oder so lange wie das Universum alt ist. Ein Beispiel aus dem Alltag: Man will über den Tag verteilt noch einige Sachen erledigen: Buch in der Bibliothek abgeben, was Essen, ein paar Sachen einkaufen, sich mit jemandem treffen. All diese Dinge finden an verschiedenen Orten statt. Wie ist die kürzeste Route von der eigenen Wohnung zu all diesen Orten und wieder zurück?
Dieses Problem ist das Traveling-Salesman-Problem und liegt in NP.
Wenn man (inklusive Wohnort) nur vier oder fünf Stationen hat, sieht man die Lösung sofort, wenn man jedoch 20 verschiedene Orte hat, die wild in der Stadt verteilt sind, gibt es über 100 Billionen Möglichkeiten, und man sieht die Lösung nicht sofort. Alle Möglichkeiten durchzutesten würde relativ lange dauern.
Aber was wäre, wenn es trotz dieser immensen Zahl einen Weg gäbe, die optimale Route mit relativ wenigen Rechenschritten zu berechnen?
P und NP
P und NP sind Namen für Problemklassen. Grob gesagt ist P die Klasse der Probleme, die sich auf einer normalen, d.h. deterministischen, Rechenmaschine1 in polynomieller Zeit lösen lassen. Genauer: Probleme, die sich in polynomiell vielen Schritten lösen lassen. Beispiel: Eine gewisse Anzahl, nennen wir diese Zahl k, Personen trifft sich. Nun soll jeder jedem die Hand schütteln - wie viele Hände-Schüttelungen müssen durchgeführt werden? Es sind (k²-k)/2. Das runden wir auf zu k². k² ist ein Polynom. Unser Händeschüttelproblem ist also in der Klasse P, weil nur es polynomiell viele Schritte braucht.
Probleme, die in P sind nennt man manchmal salopp „effizient lösbar” - das meint man im Vergleich zu den Problemen in NP.
Die Klasse NP ist die Klasse der Probleme, die sich auf einer nicht-deterministischen Rechenmaschine in polynomieller Zeit lösen lassen. Das Wort nicht-deterministisch ist hier wichtig und macht den Unterschied zur Klasse P aus. Es bedeutet, dass unsere Rechenmaschine beliebig viele Berechnungspfade erzeugen kann und es schon reicht, wenn einer davon erfolgreich beendet wird. Das klingt irgendwie ziemlich unrealistisch und man müsste denken, dass man mit solch einer abgefahrenen Maschine viel mehr Probleme in polynomieller Zeit lösen könnte, als mit der Maschine, auf der P aufbaut. Man würde also intuitiv annehmen, dass P≠NP, dass diese Klassen nicht gleich sind.
Beweis
Das zu beweisen sollte einfach sein - man muss ja nur ein Problem finden, dass in NP liegt, aber nicht in P. Also ein Problem, dass auf nicht-deterministischen Maschinen in polynomieller Zeit lösbar ist, auf normalen Maschinen jedoch nicht.
Das ist schwerer als man denkt, denn man muss nicht nur zeigen, dass es für das Problem aktuell keinen Algorithmus mit polynomieller Laufzeit gibt, sondern man muss beweisen, dass es einen solchen Algorithmus nicht geben kann.
Vinay Deolalikar hat das nun offenbar geschafft, indem er, so wie ich das sehe, einen Zusammenhang zwischen der begrenzten Reichweite von prädikatenlogischen Aussagen, physikalischer Statistik und der Problemklasse P aufgedeckt hat.
Mal sehen ob sich das bestätigt.
Update: Der Beweis ist wohl fehlerhaft, aber an einer neuen Version wird gearbeitet.
- Genauer gesagt einer Turingmaschine - aber es ist für diesen Artikel auch okay, wenn man sich einfach nur einen PC vorstellt. ↩
Tolle Erklärung! Dankeschön!
Also ich hab das so verstanden
… Man versucht zu beweisen das ein PC innerhalb von Sekunden eine Berechnung durchführen kann, wofür ein derzeitiger Computer nicht einmal in der Lage wäre bzw unendlich lange für die Berechnung bräuchte? Ist das in etwa so ahnlich wie ein normaler PC zu einem Quanten PC oder wie sich diese Art Computer nennt an denen soweit ich weis ebenfalls geforscht wird? Ich hab leider noch nicht ganz das wissen zu verstehen was mit polynomieller Laufzeit etc gemeint ist…
Es geht wirklich nur darum, wie die Formel aussieht, die beschreibt, wieviele Operationen man bei einer bestimmten Problemgröße n braucht. Beim Händeschütteln sind es eben eine quadratische Formel, also ein Polynom vom Grad 2, also ist das Händeschütteln ein Problem mit polynomieller Laufzeit.
Wichtig ist noch: Ich habe in dieser Argumentation nicht erwähnt, wie schnell die Hände geschüttelt werden! Der Grund ist, dass es nicht wichtig ist, denn angenommen ich mache, dass das es doppelt so schnell geht: was passiert dann mit der Formel für die Laufzeit? Es kommt vorn ein Faktor 0.5 dazu, aber daran, dass es ein Polynom ist, ändert sich dadurch nichts
Es geht also nicht darum, wie schnell mein Computer ist, sondern eben ob die Formel ein Polynom ist, oder etwas anderes, was schneller ansteigt Beispielsweise etwas mit exp(n) oder n! (n Fakultät) darin.
Hallo?
Ich sitze gerade im Info unterricht und tue so als würde ich arbeiten.
Moin Jungs ich bins ihr euern Rrumpelstielzchen
Ich habe dat Problem gelöst! Mich meine Jungens und ich warnse gestern aufn Sportplatz an kicen. Biste nache Schicht ine Trinkhalle gegangen ums dich ein zu Schütten und dann hamwa den Kack da kurz gelöst
P ist gleich Np
Warum?
Weil ich dat sagen tu!