Millenium-Problem für Anfänger oder P = NP?

Ein Inder, der fast so alt ist, wie das Problem, dass er in diesen Tagen gelöst glaubt, hat seinen mächtigen Lösungsvorschlag präsentiert. Sein über 100 Seiten starker Beweis kann im Internet frei betrachtet werden und ist hier abrufbar. Vinay Deolalikar hat einen Beweis erbracht, dass P und NP nicht identisch sind, wodurch eins der Millenium-Probleme gelöst scheint. Ob dieser Beweis akzeptiert wird, hängt vom Clay Mathematics Institute (CMI) ab, denn dort wurden die Millenium-Probleme ausgeschrieben und mit einem Preisgeld dotiert. Sollte der Fall eintreten, dass das CMI Deolalikars Beweis akzeptiert und bestätigt, so wird dieser um eine Million Dollar reicher.

Doch worüber rede ich hier eigentlich? Das P mit NP nicht identisch ist und sie etwas unterscheidet, erkannt man schon an ihrem Aussehen, aber hinter diesen läppischen Buchstaben versteckt sich eine Welt und ein sehr interessantes Problem. Es geht um den Aufwand den ein Computer aufbringen muss, um ein bestimmtes Problem zu lösen. Dabei wird unterschieden zwischen Problemen die in berechenbarer Zeit und nicht-berechenbarer Zeit gelöst werden können.
Was wird hier für eine Unterscheidung getroffen? Eine Lösung die in berechenbarer Zeit oder in polynomial Zeit erfolgt, umfasst eine Rechenaufgabe bei der jeder Rechenschritt gleich ist und sich ständig wiederholt, wodurch der Ablauf der Rechenaufgabe fest vorgegeben ist. Soll nun eine Lösung für ein Problem gefunden werden, dass nicht in berechenbarer Zeit, sondern nur in nicht-berechenbarer Zeit (oder in nicht-polynomialer Zeit) gelöst werden kann, so wird bei jedem Rechenschritt mit Hilfe des Zufalls eingegriffen, wodurch nicht vorhersagbar wird, wie lange diese Rechnung dauern wird.
Die Probleme, die sich leicht lösen lassen und deren Rechenablauf vorbestimmt sind, tragen den Buchstaben P, wie praktisch lösbar. Komplexere Probleme erhalten das Buchstabenpaar NP – die Negierung von P.
In der realen Welt treten diese – scheinbar idealen Probleme – natürlich auch auf. So ist es ein P-Problem, wenn nach der Lösung einer Multiplikation zweier Zahlen gefragt wird. Wie viel Zeit diese Multiplikation beansprucht, ist dabei durch einen Algorithmus errechenbar. Das NP-Problem zulösen, wird außerhalb der idealen Wissenschaften zu einer empirischen Untersuchung, denn die Frage nach dem kürzesten Weg für – zum Beispiel – die Auslieferung von Zeitungen, kann einfach ausgetestet werden.
In der Mathematik und theoretischen Informatik werden Computer angestellt, um diese Probleme zu lösen. Unabhängig von den Untersuchungen eines Zeitungsjungen, soll ein Algorithmus diese Frage nach dem schnellsten Weg oder einer Multiplikation lösen. Während die einfachen P-Probleme mit Hilfe von deterministischen Algorithmen gelöst werden, wird zur Lösung eines NP-Problems ein nicht-deterministischer Algorithmus angewendet. Ein deterministischer Algorithmus verhält sich ganz seiner Vorherbestimmung und führt nur vorbestimmte Aufgaben aus. Das Verhalten eines nicht-deterministischen Algorithmus kann nicht exakt vorhergesagt werden, da der einprogrammierte Zufall seine Hände im Spiel hat.
Wie macht die Maschine das nun? Jener einprogrammierte Zufall ist ein Zufallsbit, dessen Wert (1 oder 0) nicht errechnet werden kann und wie schon gesagt, zufällig. Diese theoretische Maschine dient als Gedankenexperiment und soll helfen NP-Probleme zu lösen. Ihren Weg in die Praxis hat sie noch nicht gefunden und wird sie wohl nicht finden, da sie nicht realisierbar scheint.

Der Inder Vinay Deolalikar hat also festgestellt, dass P nicht identisch ist mit NP. Was bedeutet das nun? Zunächst hat er einen Vorschlag geliefert, um das Verhältnis von P und NP zu klären. Die große Frage nach der Möglichkeit, ob NP-Probleme mit P-Methoden gelöst werden können, kann – sofern der Vorschlag bestätigt wird – mit einem Nein beantwortet werden und die Frage nach dem kürzesten Weg, muss wohl mit Hilfe des Zufalls gelöst werden. Ineffizient, aber eine Lösung – die beste bisher.

Schreibe einen Kommentar

Trage deine Daten unten ein oder klicke ein Icon um dich einzuloggen:

WordPress.com-Logo

Du kommentierst mit Deinem WordPress.com-Konto. Abmelden / Ändern )

Twitter-Bild

Du kommentierst mit Deinem Twitter-Konto. Abmelden / Ändern )

Facebook-Foto

Du kommentierst mit Deinem Facebook-Konto. Abmelden / Ändern )

Google+ Foto

Du kommentierst mit Deinem Google+-Konto. Abmelden / Ändern )

Verbinde mit %s

%d Bloggern gefällt das: