[HaBo]

Cyberm@ster · 10.08.10, 18:03

Zitat:

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

Zitat:

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]

t3rr0r.bYt3 · 10.08.10, 18:08

Zitat:

This work was pursued independently of my duties as a HP Labs researcher, and without the knowledge of others.

(http://gregbaker.ca/blog/2010/08/07/p-n-np/)

Anzeige

- Anzeige -

Cyberm@ster · 10.08.10, 18:28

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)

Anzeige

- Anzeige -

Themen-Optionen
Druckbare Version zeigen Jemanden per E-Mail auf dieses Thema hinweisen
Ansicht
Linear-Darstellung Zur Hybrid-Darstellung wechseln Zur Baum-Darstellung wechseln

10.08.10, 18:28	#3 (permalink)
Cyberm@ster Senior Member Themenstarter Registriert seit: 27.06.04 Likes: 0	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)

[HaBo]

Vinay Deolalikar löst P-NP-Problem