Es sieht so aus, als wäre eines der wichtigsten noch offenen Rätsel der Informatik gelöst worden. Vinay Deolalikar von den HP Reseach Labs scheint jetzt endlich bewiesen zu haben, dass die Komplexitätsklasse P ungleich der Komplexitätsklase NP ist. Die Lösung dieses Millennium-Problems ist mit 1 Million Dollar dotiert und behandelt im wesentlichen die Fragestellung „Wenn es für ein Problem einen einfachen Weg gibt, eine Lösung zu verifizieren, gibt es dann auch eine einfache Lösung?“. Mit P ≠ NP ist jetzt endlich der Beweis für die bislang allgemeine Annahme, dass dies nicht so ist, erbracht.

Ein Beispiel für ein solches Problem ist das Problem des Handlungsreisenden (Traveling Salesman Problem), bei dem es darum geht, eine bestimmte Anzahl von Städten so zu besuchen, dass ein möglichst kurzer Weg zurückgelegt wird, jedoch keine Stadt mehrmals besucht wird.

Leider wurde der Beweis relativ kurze Zeit später widerlegt.

Weiterführende Links: