Lange gesuchter Informatik-Algorithmus endlich gefunden ?
Der Mathematiker Plotnikov will einen Algorithmus entdeckt haben, der ein sogenanntes "Cliquen-Problem" aus dem Bereich der theoretischen Informatik lösen können soll. Dabei hängt die Zeit zur Lösung proportional von der Komplexität des Problems ab.
Zu den NP-Problemen gehört z.B. der "Traveling Salesman", der eine Reihe von Städten besuchen will, ohne eine öfter als einmal zu besuchen. Der gefundene Algorithmus soll eine Menge von teilweise verbundenen Punkten in Teilmengen zerlegen können, in
denen jeweils alle Punkte miteinander verbunden sind.
Bisher waren viele der Ansicht, einen solchen Algorithmus könne es gar nicht geben, man behalf sich mit Näherungen. Falls der Algorithmus funktioniert, könnte das ganz neue Ansätze darstellen.
129
