Was bedeutet „P vs. NP“ für den Rest von uns?

Programmierer und Informatiker schwirren seit einer Woche um den neuesten Versuch, eine der brisantesten Fragen der Informatik zu lösen: das sogenannte P-gegen-NP-Problem.

Vinay Deolalikar, ein Forscher bei HP Labs in Palo Alto, CA, hat seinen Beweis online gestellt und am 6. August an mehrere Experten auf diesem Gebiet geschickt. Kollegen begannen sofort, den Beweis in akademischen Blogs und Wikis zu analysieren. Die ersten Reaktionen waren respektvoll, aber skeptisch, und der aktuelle Konsens ist, dass Deolalikars Ansatz grundlegend fehlerhaft ist.

Ein solider Beweis würde Deolalikar Ruhm und Reichtum einbringen. Der Lehm-Mathematik-Institut in Cambridge, MA, hat P im Vergleich zu NP als eines seiner Millennium-Probleme genannt und bietet jedem, der einen verifizierten Beweis vorlegt, 1 Million US-Dollar.



Aber P versus NP ist mehr als nur ein abstraktes mathematisches Puzzle. Es versucht ein für alle Mal festzustellen, welche Arten von Problemen durch Computer gelöst werden können und welche nicht. Probleme der P-Klasse sind für Computer leicht zu lösen; das heißt, Lösungen für diese Probleme können im Vergleich zur Komplexität des Problems in angemessener Zeit berechnet werden. Für NP-Probleme kann es jedoch sehr schwer sein, eine Lösung zu finden – möglicherweise erfordert dies Berechnungen im Wert von Milliarden von Jahren –, aber wenn sie einmal gefunden ist, kann sie leicht überprüft werden. (Stellen Sie sich ein Puzzle vor: Die richtige Anordnung der Teile zu finden ist schwierig, aber Sie können beim Anschauen erkennen, wann das Puzzle richtig fertig ist.)

Probleme der NP-Klasse umfassen viele Mustervergleichs- und Optimierungsprobleme, die von großem praktischen Interesse sind, wie die Bestimmung der optimalen Anordnung von Transistoren auf einem Siliziumchip, die Entwicklung genauer Finanzprognosemodelle oder die Analyse des Proteinfaltungsverhaltens in einer Zelle.

Das P-gegen-NP-Problem fragt, ob diese beiden Klassen tatsächlich identisch sind; das heißt, ob jedes NP-Problem auch ein P-Problem ist. Wenn P gleich NP ist, enthält jedes NP-Problem eine versteckte Verknüpfung, die es Computern ermöglicht, schnell perfekte Lösungen dafür zu finden. Aber wenn P nicht gleich NP ist, dann gibt es keine solchen Abkürzungen, und die Problemlösungsfähigkeiten von Computern bleiben grundsätzlich und dauerhaft begrenzt. Praktische Erfahrungen legen überwiegend nahe, dass P nicht gleich NP ist. Aber bis jemand einen soliden mathematischen Beweis liefert, bleibt die Gültigkeit der Annahme fraglich.

Selbst wenn sich der Beweis von Deolalikar als stichhaltig erweisen sollte, bleibt die Frage, welche Auswirkungen ein solcher Beweis auf relevante Bereiche der Informatik haben würde.

Oberflächlich betrachtet könnte man meinen, die Antwort sei nicht viel. Der Beweis, dass P nicht gleich NP ist, würde nur bestätigen, was fast jeder für praktische Zwecke bereits als wahr annimmt, erklärt Scott Aaronson , einem Komplexitätsforscher am Computer Science and Artificial Intelligence Laboratory des MIT.

Zum Beispiel bildet unsere Unfähigkeit, riesige zusammengesetzte Zahlen (ein klassisches NP-Problem) effizient zu faktorisieren, die Grundlage der modernen Kryptographie – die alles von der nationalen Sicherheit bis hin zu Amazon.com-Käufen untermauert. Wir brauchen keinen formalen Beweis, dass P nicht gleich NP ist, um uns auf die Vermutung zu verlassen, sagt Aaronson. Programmierer kennen das Problem und wären begeistert zu sehen, dass P nicht gleich NP ist, bewiesen, aber im Alltag wissen sie, dass es viel sinnvoller ist, [ein NP-Problem] in etwas einfacheres umzuformulieren, als zu versuchen, das mathematische zu lösen Jahrhundertproblematik.

Da Probleme der NP-Klasse so allgegenwärtig sind (sogar Sudoku-Rätsel und die Suche nach Flugplänen auf Bing.com sind rechenintensiv), werden ständig innovative Problemumgehungen entdeckt. Die stochastische Optimierung ahmt beispielsweise die Zufälligkeit in physikalischen Systemen nach (z. B. beim Kühlen von Metallen oder mutierender DNA), um ausreichend gute Lösungen anstelle von rechenintensiven Lösungen zu produzieren.

Versuche, mit der Annahme umzugehen, dass P nicht gleich NP ist, helfen uns, neue mentale Technologien zu entwickeln, sagt Richard Lipton , ein Informatiker an der Georgia Tech, der das P-gegen-NP-Problem untersucht. Obwohl wir seit Jahrzehnten Algorithmen schreiben, verstehen wir nicht ganz, wozu sie fähig sind, fährt er fort. Selbst wenn Sie also beweisen würden, dass P nicht gleich NP ist – etwas, an das bereits jeder glaubt – müsste es unser Verständnis dieser Fähigkeiten radikal erweitern und viele neue Dinge mit Computern ermöglichen, zusätzlich zu all den cleveren Workarounds, die wir bereits haben gefunden.

Wenn also inkrementeller Fortschritt immer noch nützliche Innovationen hervorbringen kann, warum widmen Titanen der industriellen Forschung wie Google, Microsoft und HP (die alle keinen Kommentar zu diesem Artikel abgegeben haben) riesige Forscherteams dem P-gleich-NP-Puzzle? Ein Negativ zu beweisen ist einfach unglaublich schwer, und aus der Sicht eines großen Unternehmens hat es wahrscheinlich keine großen Auswirkungen auf das nächste Finanzquartal oder sogar die nächsten Jahre ihres Geschäfts, sagt Lipton. Es ist eher ein langfristiges Thema.

Natürlich gibt es immer die Alternative: zu beweisen, dass P tut tatsächlich gleich NP. Aber halten Sie nicht den Atem an, sagt Aaronson. Es gibt gute Gründe, warum nur sehr wenige Leute glauben, dass P gleich NP ist, sagt er. Wenn dies der Fall wäre, würden wir in einem grundlegend anderen Universum leben, und wir hätten es wahrscheinlich schon bemerkt.

verbergen