Millenniumsrätsel der Mathematik gelöst?
Eine Million - nein, danke!
Im Jahr 2000 hat das Clay Mathematics Institute im amerikanischen Cambridge Preise von je einer Million US-Dollar für die Lösung der sieben Millenniumsprobleme ausgeschrieben. Dem russischen Mathematiker Grigoriy Perelman ist es mit dem Beweis der Poincare-Vermutung vor vier Jahren tatsächlich gelungen, eines der Rätsel zu lösen. Zum Preisgeld sagte der kauzige Wissenschaftler heuer allerdings: "Nein, danke".
Nun besteht ernsthaft die Möglichkeit, dass die Million erstmals wirklich vergeben wird: Der indische Mathematiker Vinay Deolalikar von den Hewlett-Packard Labs behauptet, ein weiteres der überaus kniffligen Rätsel gelöst zu haben. Formuliert wurde das "P vs. NP-Problem" erstmals und unabhängig voneinander von Stephen Cook and Leonid Levin im Jahr 1971.
Die Studie:
"P ≠ NP" von Vinay Deolalikar auf der Website der HP Labs.
Eine Frage der Komplexität
Rein formal sieht die Lösung von Deolalikar gar nicht kompliziert aus. Sie lautet: P ist nicht gleich NP. Etwas komplizierter wird es, wenn man verstehen will, was das bedeutet. science.ORF.at hat dazu mit Reinhard Pichler von der Fakultät für Informatik der Technischen Universität Wien gesprochen.
Der Hintergrund der Fragestellung kommt aus der Komplexitätstheorie, einem wichtigen Zweig der theoretischen Informatik. Sie geht Fragen nach wie: Kann es für bestimmte Probleme überhaupt ein - relativ - schnelles Lösungsverfahren geben? Was geschieht, wenn das nicht der Fall ist?
"Dann haben die beteiligten Mathematiker oder Informatiker entweder nicht lange genug gesucht, oder die inhärente Komplexität der Probleme ist zu groß, sodass es niemals ein effizientes Lösungsverfahren geben wird", beantwortet Pichler diese Fragen.
Polynomielle und andere Probleme
Die Grenze zwischen effizient lösbaren und nicht-effizient lösbaren Problemen bestimmt in der Komplexitätstheorie die benötigte Rechenzeit: Erstere sind in polynomieller Zeit lösbar, letztere nur in exponentieller.
Genau hier setzt das Millenniumsproblem von "P vs. NP" an. P ist nämlich jene Klasse aller Probleme, die sich in polynomieller Zeit lösen lassen. NP hingegen steht für die Klasse aller Probleme, die sich in - ja, so heißt das - nondeterministisch-polynomieller Zeit lösen lassen.
"D. h., es gibt für diese Klasse von Problemen eine polynomielle Lösung, sprich eine - relativ - einfache Lösung, und es lässt sich für eine einmal gefundene Lösung relativ leicht verifizieren, dass sie tatsächlich eine Lösung ist. Das Problem aber ist: Finden muss man sie! Der Suchraum dieser Probleme ist nämlich exponentiell groß", erklärt Pichler.
Bestätigung der Praxis
NP-Probleme befinden sich somit in einer gewissen Zwischenposition zwischen polynomiell und exponentiell lösbaren Problemen. Wenn Vinay Deolalikar recht hat, dann unterscheiden sich P und NP grundlegend.
In der Praxis wird sich dadurch wenig ändern, denn: "Bisher haben wir in der Mathematik gesagt: Für NP sind keine polynomiellen Verfahren bekannt. Nun könnte es heißen: Für diese Probleme kann es keine polynomiellen Verfahren geben", so Reinhard Pichler.
Beispiel Maschinenbelegung
Apropos Praxis: Was so theoretisch daherkommt, begegnet uns im Alltag auf Schritt und Tritt. Ein Beispiel für ein Problem der Klasse NP ist die Maschinenbelegung eines rohstoffverarbeitenden Unternehmens. Aus der Sicht der Komplexitätstheorie gibt es dabei mehrere Faktoren: den Werkstoff, das Personal, Strom etc. und - am wichtigsten - verschiedene Zeitpunkte.
Die Frage lautet, wie sich diese Faktoren am effizientesten kombinieren lassen. Mit anderen Worten: Wie viele und welche Arbeiter müssen zu welchem Zeitpunkt welche Aktion setzen, um das gewünschte Resultat zu erzielen?
Der Suchraum des Problems ist exponentiell, die Lösung selbst relativ klein und auch relativ einfach verifizierbar (ein konkreter Belegungsplan: Am Montag beladen drei Personen die Maschine XY mit folgendem Material ...).
Die Mathematikergemeinde tagt
Ein anderes Beispiel ist der Stundenplan einer Schule, bei dem Lehrer, Klassen, Fächer und Räume kombiniert werden müssen. Selbst bei der heute dafür verwendeten Software kommt selten ein wirklich optimales Ergebnis zustande. Zwar schaffen es die Programme, zu verhindern, dass etwa ein Lehrer parallel in zwei Klassen stehen muss. Dass er oder sie vielleicht zwei Stunden Leerphase hat, kann aber nicht verhindert werden.
Mit der möglichen Lösung von "P ≠ NP" ist den Lehrern nun nicht unbedingt geholfen. "Sie werden weiter Löcher im Unterrichtszeitraum haben. Aber sie wissen jetzt wenigstens, dass sie nicht darauf warten müssen, dass jemand ein effizientes und geschlossenes Verfahren für dieses Problem entwickeln wird", meint Reinhard Pichler.
Ob dem wirklich so ist, wird die Gemeinde der Mathematiker entscheiden. "Problemerfinder" Stephen Cook hat in einer ersten Reaktion von einem "relativ seriösen Lösungsansatz" gesprochen. Auf Blogs wie Gödels Lost Letter ist man eher skeptisch. Vinay Deolalikar selbst hat auf mehrere Einwände bereits reagiert und Neuerungen in seine Arbeit einfließen lassen.
Lukas Wieselberg, science.ORF.at
Mehr zu dem Thema:
- Eine Million Dollar Preisgeld: "Nein, danke"
- Mathematik: Nichts als Probleme
- Beweis der Poincare-Vermutung
- Mathematik: Die Last des Beweises
