Vinay Deolalikar löst P-NP-Problem

Cyberm@ster

New member
Das P-NP-Problem (auch P≟NP, P versus NP) ist ein ungelöstes Problem der Mathematik und theoretischen Informatik, speziell der Komplexitätstheorie. Es stellt die Frage, in welcher Beziehung die beiden Komplexitätsklassen P und NP stehen. Erkannt wurde das Problem zu Beginn der 1970er-Jahre aufgrund unabhängig voneinander erfolgter Arbeiten von Stephen Cook und Leonid Levin. Das P-NP-Problem gilt als eines der wichtigsten offenen Probleme der Informatik und wurde vom Clay Mathematics Institute in die Liste der Millennium-Probleme aufgenommen. Quelle: Wikipedia

Als Millennium-Probleme bezeichnet man die im Jahr 2000 vom Clay Mathematics Institute (CMI) in Cambridge (Massachusetts) festgesetzte Liste ungelöster Probleme der Mathematik. Das Institut in Massachusetts hat dafür ein Preisgeld von jeweils einer Million US-Dollar für die Lösung eines der sieben Probleme ausgelobt. Quelle: Wikipedia

Wie es aussieht hat HP (oder vielmehr Vinay Deolalikar) jetzt dieses wichtige Problem der Mathematik / Computerwissenschaften gelöst indem der Beweis erbracht wurde, dass P != NP ist.


Für die Mutigen unter euch: der Beweis [PDF]
 
Zuletzt bearbeitet:

Cyberm@ster

New member
Danke für die Richtigstellung, von der E-Mail wusste ich nichts.

Das Resultat entspricht zwar leider nicht dem erhofften Ergebnis aber immerhin haben wir jetzt Gewissheit... (wenn der Beweis bestätigt wird) :rolleyes:
 
Oben