Als jemand der Informatik studieret und dabei die theoretische Aspekte liebt, hat mich heute ein kleiner circa 50 Wörter langer Artikel in der c’t 18/2010 in helle Aufregung versetzt. (Ausführlicher Artikel von heise siehe Link am Ende)

Demnach soll ein amerikanischer Wissenschaftler, der bei HP Labs angestellt ist, das N-NP-Problem gelöst haben. Dieses Problem wurde mir wohl schon im ersten Semester vermittelt. Meine Professoren nannten es als eines der schwierigsten Probleme unserer Zeit, das nicht bewiesen oder widerlegt werden kann (konnte?). Die Frage ist ob sich Probleme, die mit deterministischen (streng algorithmisch ohne Zufallswahl) Turing-Maschinen (Beispiel: Computer) nur in nicht-polynomieller Zeit lösen lassen, vielleicht doch polynomiell lösen lassen. Alle Probleme, die sich in polynomieller Zeit mit einer deterministischen Turing-Maschine (Computer) lösen lassen sind in der Menge P, alle die sich nur mit einer nichtdeterministschen Turing-Maschine (in einem Zwischenschritt wird zufällig das richtige Vorgehen erraten) in polynomieller Zeit lösbaren Probleme in NP. Die Frage ist also ist P gleich zu NP.

Da das Problem so schwierig ist, gehört es zusammen mit sechs (eins wurde bereits 2002 gelöst)) fünf anderen offen Fragen zu den sieben Millennium-Problemen, deren Beantwortung dem Clay Mathematics Institute eine Million Dollar wert ist. Vinay Deolalikar soll das Kunststück der Lösung jetzt gelungen sein. Nach seinem Beweis gilt P != NP. Sollte sich das als wahr herausstellen, sind typische NP-Probleme wie das Travelling-Salesman-Problem (weitere fallen mir auf Anhieb nicht ein) in akzeptabler (polynomieller) Rechenzeit nicht lösbar. Leider hat ein Forscher schon Bedenken angemeldet und zwei fatale Fehler benannt. Für einen normalen Student, wie mich, ist wahrscheinlich weder der Beweis noch die Fehler nachvollziehbar, dennoch ist es enorm spannend. Sollte sich der Beweis erhärten, ist ein Grundproblem, dass für mich als für immer offen galt, nicht mehr offen.

Artikel: