zurück zum Artikel

Eines der wichtigsten bislang ungelösten Probleme der Mathematik scheint enträtselt: Vinay Deolalikar von den HP Research Labs hat eine Arbeit vorgestellt, die beweisen soll, dass die Komplexitätsklassen P und NP nicht identisch sind.

Eines der wichtigsten offenen Probleme, mit denen sich Mathematiker und theoretische Informatiker herumschlagen, scheint gelöst: die Frage, ob die beiden so genannten Komplexitätsklassen P und NP identisch sind oder nicht. Der bei den HP Labs [1] im kalifornischen Palo Alto beschäftigte Forscher Vinay Deolalikar [2] behauptet, sie sind es nicht, und hat dafür einen knapp einhundertseitigen Beweis (PDF [3]) vorgelegt.

In der Komplexitätstheorie umfasst die Klasse P all die Probleme, die sich mit einer deterministischen Rechenmaschine in einer Rechenzeit t lösen lassen, die von der Größe der Eingangsdaten n höchstens polynomisch abhängt, das heißt t ≤ n^k. Als Modell einer deterministischen Rechenmaschine verwenden Theoretiker üblicherweise eine Turing-Maschine, aber auch alle herkömmlichen digitalen Computer gehören dazu. Die Komplexitätsklasse P umfasst also alle Aufgabenstellungen, die sich mit vertretbarer Rechenzeit exakt berechnen lassen.

Die theoretische Informatik kennt neben deterministischen Automaten noch andere Modelle, darunter die nichtdeterministische Turing-Maschine: Sie entscheidet sich bei jedem Rechenschritt zufällig für einen von mehreren möglichen Wegen, die Berechnung fortzusetzen; der genaue Ablauf der Berechnung ist nicht von vornherein bestimmbar. Probleme, die eine solche Maschine in Polynomialzeit lösen kann, bilden die Komplexitätsklasse NP.

P ist eine Teilmenge von NP, denn Probleme, die sich deterministisch in Polynomialzeit lösen lassen, können auch nichtdeterministisch mit polynomischem Aufwand berechnet werden. Die bislang unbeantwortete Frage lautet, ob das auch umgekehrt gilt oder nicht. Etwas salopp formuliert: Könnten nichtdeterministische Maschinen bestimmte Rechenprobleme schneller lösen als bisherige Computer? Genau diese Frage bejaht Deolalikar nun in seinem Papier.

Die Arbeit ist ganz frisch und noch nicht ausführlich von Kollegen geprüft. Der HP-Forscher gilt aber als Experte auf diesem Forschungsgebiet und erste Einschätzungen halten die Arbeit für stichhaltig. Ob sie genaueren Prüfungen standhält, wird sich noch zeigen müssen, aber dass es diese Prüfungen geben wird, kann als sicher gelten: Immerhin ist das P-NP-Problem eines von sieben Fragestellungen, die das Clay Mathematics Institute (CMI [4]) in Cambridge in die Liste der so genannten Millennium-Probleme [5] aufgenommen und für deren Lösung es jeweils ein Preisgeld von einer Million US-Dollar ausgelobt hat. (hos [6])

URL dieses Artikels:
https://www.heise.de/-1052857

Links in diesem Artikel:
[1] http://www.hpl.hp.com/
[2] http://www.hpl.hp.com/personal/Vinay_Deolalikar/
[3] http://www.win.tue.nl/~gwoegi/P-versus-NP/Deolalikar.pdf
[4] http://www.claymath.org/
[5] http://www.claymath.org/millennium/
[6] mailto:hos@ct.de

Copyright © 2010 Heise Medien