P != NP möglicherweise bewiesen

Dieses Thema im Forum "Netzwelt" wurde erstellt von SHiDO, 13. August 2010 .

  1. 13. August 2010
    P != NP möglicherweise bewiesen!

    Eines der wichtigsten offenen Probleme, mit denen sich Mathematiker und theoretische Informatiker herumschlagen, scheint gelöst: die Frage, ob die beiden so genannten Komplexitätsklassen P und NP identisch sind oder nicht. Der bei den HP Labs im kalifornischen Palo Alto beschäftigte Forscher Vinay Deolalikar behauptet, sie sind es nicht, und hat dafür einen knapp einhundertseitigen Beweis (PDF) vorgelegt.

    In der Komplexitätstheorie umfasst die Klasse P all die Probleme, die sich mit einer deterministischen Rechenmaschine in einer Rechenzeit t lösen lassen, die von der Größe der Eingangsdaten n höchstens polynomisch abhängt, das heißt t ≤ n^k. Als Modell einer deterministischen Rechenmaschine verwenden Theoretiker üblicherweise eine Turing-Maschine, aber auch alle herkömmlichen digitalen Computer gehören dazu. Die Komplexitätsklasse P umfasst also alle Aufgabenstellungen, die sich mit vertretbarer Rechenzeit exakt berechnen lassen.

    [...]

    Quelle: Heise.de

    Der Beweis: PDF

    -------------------------------------------------------

    Das zweite der sieben Millenium Probleme gelöst? Und dann auch noch das wahrscheinlich Bekannteste? Wäre schon eine riesen Nummer.
    Der Beweis selbst ist eher kurz, das PDF-Dokument enthält auch viel Wissen, welches benötigt wird um vielleicht ansatzweise zu verstehen, worum es überhaupt geht. Auf jedenfall heißt es erstmal abwarten ob der Beweis hält. Wenn dies so wäre kann man Vinay Deolalikar gratulieren. Ob er die eine Million Dollar alleine bekommen würde?
    Auf jedenfall ist es ein großer Schritt in Richtung Lösung. Ob es die Lösung nun schon ist, werden wir sehen.
     
  2. 13. August 2010
    AW: P != NP möglicherweise bewiesen

    Leider sind meine Mathematik-Kenntnisse unzureichend, um den Beweis verstehen zu können, allerdings ist die Thematik sehr interessant, das wäre dann nach Perelman schon der zweite, der dieses Jahrzehnt ein Millenium-Problem knackt. Mittlerweile melden sich aber auch viele Experten zu Wort, die an dem Beweis zweifeln. Deolalikar ist ja fröhlich am Updaten des Papers.
    Naja auch viele andere Beweise mussten nachträglich verbessert werden, schauen wir mal wie sich das entwickelt. Es gab schon viele Ansätze zu P-NP, die sich schlussendlich als falsch rausgestellt haben.
     
  3. 13. August 2010
    AW: P != NP möglicherweise bewiesen

    kann das mal einer in nem knappen satz sagen was der artikel nun aussagt? und was man davon hat?

    naja 66 seiten sind ned knapp 100. das is fast die hälfte.
     
  4. 13. August 2010
    AW: P != NP möglicherweise bewiesen

    Wie SHiDO und lolkind bereits erwähntee, gibt es für die Lösung dieser Aufgabe ein Preisgeld von 1 Million Dollar vom Clay Institut. Man kann sich vorstellen, dass das Problem also komplex ist, aber ich kann ja mal versuchen zusammenzufassen, was dieses Problem ist :
    Zuerst die Zusammenfassung:

    Die Frage ob P=NP ist ist die Frage, ob Probleme deren vermeindliche Lösung leicht auf Richtigkeit zu überprüfen ist auch leicht zu lösen sind.



    Nun eine kleinere mathematische Erläuterung im Spoiler:
    Spoiler
    P und NP sind Klassen, in welche man gegebene Probleme einordnen kann.

    P steht für " polynomial ", das heißt dass zu einem gewissen Input x sich die Rechenzeit mit einer bestimmten fruchtbarkeit n anwächst . Zum beispiel möchte ich prürfen ob die Zahl q eine primzahl ist oder nicht, dann könnte der Prozess der dies prüft beispielsweise die Rechenzeit q² haben. (Rein ersponnenes Beispiel, zudem ist "Rechenzeit" ein nicht ganz korrekter Begriff, es geht vielmehr um die Komplexität, also ein bisschen allgemeiner als Rechenzeit")

    NP steht für " nichtdeterministisch polynomial ", was soviel heißen will, dass ich für eine vorgeschlagene Lösung des Problems in aktezptabler Zeit rausfinden kann, ob sie richtig ist oder falsch.


    Das Interessante an der Sache ist die sogennante NP-Vollständigkeit, denn NP-vollständige Probleme sind eine Unterklasse der NP-Probleme. Für sie gilt : eine effiziente Lösung eines dieser Probleme kann dazu dienen jedes andere NP-Problem zu lösen bzw. findet man ein effizientes Lösungsverfahren für irgendein NP-Vollständiges Problem, so hat man bewiesen, dass Alle NP-Probleme auch P-Probleme sind.
    Nun zur Frage:
    Also ihr wollte bestimmt nicht hören, was für ein tolles mathematisches Problem das ist, was es ist also ein wenig Konkreteres

    Die Frage nach N=NP könnte z.B. bei Bankgeschäftssicherheit eine Rolle spielen. Wenn ein Algrotithmus der deine Kontodatenverschlüsselt NP-Vollständig ist, könnte das Verfahren unsicher sein.

    Z.B. Konkret könnte ich mir vorstellen, dass sich die Frage auftut, wenn P=NP gilt, ob das RSA Verfahren sicher ist. Also allgemein ist die Fragestellung für das Thema "sichere Verschlüsselung" wichtig.

    Wobei wir uns ja anscheinend keine Sorgen machen müssen, wenn P!= NP gilt. ( Also P nicht gleich NP)

    Aber eben auch um zu bestimmen wie komplex vielleicht manche Probleme sind, ob man eine effiziente Lösungsmehtode finden kann ( man denke hier z.B. an das Handlungsreisenproblem, wo man versucht einen optimierten Weg durch eine Anzahl von Städten zu finden)
     
  5. 13. August 2010
    AW: P != NP möglicherweise bewiesen

    hab ich das jetzt richtig verstanden, dass P den Lösungsweg zu einem problem angibt, in "rechenzeit" oder "komplexität" und NP die überprüfung der Lösung?
    und dass es in dem beweis darum ging zu belegen, dass NP nicht gleich P ist?

    wenn das so ist, wie ich das verstanden hab ist das doch garnicht schwer zu belegen... am beispiel eines matematischen problems:

    wurzeln ziehen ist viel komplexer als quadrieren...


    SQRT ( x ) = ? <- P
    ( SQRT ( x ) ) ² = x <- NP

    das is ja für x = 9 noch relativ einfach:

    SQRT ( 9 ) = 3
    3 ² = 9
    q.e.d.

    aber für z.B. x = 65465498,23687458 wirds dann schon schwieriger (komplexer) die wurzel zu ziehen, als dieses ergebnis dann mit sich selbst zu multiplizieren (auch für einen computer)... somit ist NP != P




    oder hab ich das ganze falsch verstanden? dann bitte für mich nochmal erklären
     
  6. 13. August 2010
    AW: P != NP möglicherweise bewiesen

    na toll und ich muss nächstes semester die vorlesung dazu besuchen -.-....
    macht einen das leben nicht leichter, falls der bis dahin schon als korrekt ausgezeichnet wird...

    aber coole sache und wenns stimmt, hat er die 1mio preisgeld verdient^^
     
  7. 13. August 2010
    AW: P != NP möglicherweise bewiesen

    Heise Zitat
    Beispiel für NP-Problem hier
     
  8. 13. August 2010
    AW: P != NP möglicherweise bewiesen

    Joar fast, mag ne ungenaue Formulierung sein, aber P und NP sind "Klassen" von Problemen, das heißt nicht das NP sowas wie "der schritt zur Überprüfung ist". Wenn z.B. die Frage ist, ab welchem Wert du mit einer bestimmten Stückelung von Geld alle Beträge ausdrücken kannst, dann ist das erstmal ein Problem was zu NP gehört.

    Genauso sind auch Faktorisierungsprobelme zu NP gehörig. Und hier ist auch klar dass ich schneller checken kann, ob das Produkt zweier Zahlen die gesuchte Zahl ergibt, als diese beiden Faktoren zu finden.

    Jedoch kann das Checken ob die Lösung richtig ist ja auch schneller gehn, es geht aber darum, dass die Lösung noch immer "schnell" ist xD. Nur weil du nicht schnell im Wurzel ziehen bist, ist damit noch lange kein beweis für eine unendlich große Klasse gegeben xD Nebenbei : Der Algorithmus für Quadratwurzelziehen ist ein sehr schneller, glaube ich zumindest, sofern es das babylonische Wurzelziehen ist.

    Nebenbei wollte ich noch anmerken , dass NP probleme eine Obere Schranke der Komplexität haben. Die Frage wäre also ob die schwersten NP Probleme ebenso effizient gelöst werden können wie die P-Probleme, die natürlich alle in den NP liegen.
     
  9. 13. August 2010
    AW: P != NP möglicherweise bewiesen

    hurra ich bin nicht zu blöd, meine probleme lassen sich einfach nur nicht lösen xD

    also dafür nen mathematischen beweis aufzustellen ist doch schon echt eine kunst weil sich komplexe probleme eben nicht auf mathematik runterrechnen lassen können. und sein wir doch mal erlich: diese erkenntniss das sich manche probleme eben nur durch raten oder ausprobieren gelöst werden können wissen wir doch schon spätestens seit der 10 klasse....
    das is doch genauso idiotisch als ob man beweisen will das ein apfel keine birne ist und das bitte mathematisch...
    is ja alles schön und gut was die nerds der welt so produzieren aber manchmal sollten die echt mal mathe mathe sein lassen und mal ein bissel den gesunden menschenverstand anwerfen


    achso mein glückwunsch zur millionen... der erste musste es doch an mütterchen russland abgeben oder xD
     
  10. 13. August 2010
    AW: P != NP möglicherweise bewiesen

    ich hoffe schwer, dass die aussagen nach deiner ersten spaßig gemeint waren, denn ansonsten muss ich dir sagen dass dein erster satz vl. doch nicht stimmt xD

    Aber zum eigentlichen:
    Abtreten an Mütterchen Russland: Soweit ich weiß hat Perelman das Geld nicht angenommen, da ihm die Ehre dieses Problem gelöst zu haben, Belohnung genug war. Das Geld ist noch am Clay Insitut.
     
  11. 13. August 2010
    AW: P != NP möglicherweise bewiesen

    danke
    gut, dass nicht jeder so denk wie du, sonst wären wir nämlich noch im mittelalter.

    mal n bissl nachdenken, was man von sich gibt. ohne forschung keine entwicklung. auch wenns megakompliziert aussieht, ich wette irgendwann, wenn auf basis dieser beweise weitergeforscht werden kann, betriffts, wenn auch nur indirekt, auch dich.

    sorry für den bösen schachtelsatz^^
     
  12. Video Script

    Videos zum Themenbereich

    * gefundene Videos auf YouTube, anhand der Überschrift.