#1 P ungleich NP?
Verfasst: Sa 19. Aug 2017, 16:26
Eine zentrale und grundsätzliche Frage in der Informatik ist die Frage ob die Probleme, deren Lösung mit dem Computer in polynomialer Zeit möglich sind (Die Klasse der P Probleme) ungleich ist der Klasse der Probleme, die nicht in polynomialer Zeit (sondern exponentieller) Zeit möglich ist (Klasse der NP Probleme).
Die Antwort ist ziemlich entscheidend für viele Fragestellungen insbesondere auch die der Sicherheit von kryptografischen Verfahren.
Die Frage ergibt sich, weil es sein kann, dass man die Probleme, zu denen man nur eine exponiell wachsende Lösung kennt, vielleicht nur falsch angegangen werden.
Die Lösung der Frage, ob P gleich NP ist oder nicht, ist eines der Jahrtausendprobleme, für die hohe Preisgelder ausgelobt sind.
Nun behauptet ein Bonner Professor, die Frage gelöst zu haben und zwar dahingehend, dass P ungleich NP ist.
http://www.spektrum.de/news/loesung-fue ... tent=heute
Die Prüfung seiner Argumentation beginnt jetzt. Für ihn spricht, dass seine Argumentation solide erscheint und gut bekannte Techniken aus der Mathematik verwendet.
Gegen ihn spricht, dass es unwahrscheinlich scheint, dass Mathematiker auf die sehr traditionelle Argumentation nicht früher gestoßen sind und dass bisher mehr als 150 solcher Beweise veröffentlicht wurden, die sich allesamt als falsch herausgestellt haben.
Die Antwort ist ziemlich entscheidend für viele Fragestellungen insbesondere auch die der Sicherheit von kryptografischen Verfahren.
Die Frage ergibt sich, weil es sein kann, dass man die Probleme, zu denen man nur eine exponiell wachsende Lösung kennt, vielleicht nur falsch angegangen werden.
Die Lösung der Frage, ob P gleich NP ist oder nicht, ist eines der Jahrtausendprobleme, für die hohe Preisgelder ausgelobt sind.
Nun behauptet ein Bonner Professor, die Frage gelöst zu haben und zwar dahingehend, dass P ungleich NP ist.
http://www.spektrum.de/news/loesung-fue ... tent=heute
Die Prüfung seiner Argumentation beginnt jetzt. Für ihn spricht, dass seine Argumentation solide erscheint und gut bekannte Techniken aus der Mathematik verwendet.
Gegen ihn spricht, dass es unwahrscheinlich scheint, dass Mathematiker auf die sehr traditionelle Argumentation nicht früher gestoßen sind und dass bisher mehr als 150 solcher Beweise veröffentlicht wurden, die sich allesamt als falsch herausgestellt haben.