Informatik-Problem P=NP möglicherweise geknackt
Ein ukrainischer Forscher will das klassische Problem P=NP der Theoretischen Informatik gelöst haben.
Wie im Usenet bekannt wurde, hat der ukrainische Mathematiker Anatoly D. Plotnikov bereits vor einigen Wochen im Internet einen Algorithmus veröffentlicht, der eines der so genannten Cliquen-Probleme aus der Theoretischen Informatik in polynomieller Zeit lösen soll. Dabei geht es darum, eine gegebene Menge von Punkten, die teilweise miteinander in Verbindung stehen, so zu zerlegen, dass in den entstehenden Teilmengen jeweils alle Punkte untereinander verbunden sind. Plotnikovs Algorithmus soll dieses Problem mit einem Zeitaufwand lösen, der proportional der Anzahl der Punkte hoch sechs ist.
Während dieses Problem selbst in der Praxis eher selten auftreten dürfte, wären die Auswirkungen auf die theoretische Forschung immens: Das Cliquen-Problem ist seit langem als NP-vollständig bekannt. Dies bedeutet insbesondere, dass ein Lösungalgorithmus, der in polynomieller Zeit arbeitet (im Gegensatz zu bisherigen Algorithmen, deren Zeitbedarf exponentiell mit der Problemgröße wächst), bereits garantieren würde, dass alle Aufgaben der Klasse NP polynomielle Lösungsalgorithmen besitzen. Ob diese Vermutung , die in der Informatik mit P=NP abgekürzt wird, zutrifft, ist eines der größten offenen Probleme der Komplexitätstheorie.
Zur Klasse der NP-Probleme gehört beispielsweise auch das bekannte Problem Traveling Salesman: Ein Vertreter möchte der Reihe nach eine bestimmte Anzahl Städte bereisen, die unterschiedliche Entfernungen voneinander besitzen, ohne eine Stadt doppelt zu betreten. In welcher Reihenfolge soll er die Städte besuchen?
Dass für Fragen wie diese bisher kein effizienter Algorithmus existierte (und viele meinten, einen solchen könne es gar nicht geben), beflügelte die Fantasie vieler Programmierer und Forscher dazu, neue Techniken zu entwickeln. Oft behalf man sich mit geschickten Näherungsverfahren, das heißt, man verzichtete darauf, den besten Weg durch die Städte zu finden und suchte einfach einen sehr guten. Doch auch die zur Zeit erforschten Quantencomputer sollen ihre Leistungsfähigkeit an dieser Aufgabe beweisen.
Falls sich nun herausstellt, dass es auch einen direkten Weg zur Lösung dieser Probleme gibt, könnte die Forschung in Zukunft eine völlig neue Richtung nehmen. Doch bis es soweit ist, kann noch einige Zeit vergehen: Bislang gibt es weder eine Bestätigung noch eine Widerlegung von unabhängiger Seite. (Christoph Lampert) (ts)
