P ungleich NP?

Alle Themen aus Naturwissenschaft & Technik die nicht in die Hauptthemen passen.
Antworten
ThomasM
Beiträge: 5648
Registriert: Mo 20. Mai 2013, 19:43

P ungleich NP?

Beitrag von ThomasM »

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.
Gott würfelt nicht, meinte Einstein. Aber er irrte. Gott nutzt den Zufall - jeden Tag.
Benutzeravatar
Pluto
V.I.P.
Beiträge: 43663
Registriert: Mo 15. Apr 2013, 23:56
Wohnort: Deutschland

Re: P ungleich NP?

Beitrag von Pluto »

Wenn du mich fragst (wer tut denn so was? :o) hat der Professor recht.
Ein NP-Problem ist wesentlich komplexer als ein polynomielles Problem.

Interessanterweise hängt die Frage, ob es prinzipiell möglich ist, dass wir in einer Art Matrix leben, mit dieser Frage zusammen.
Steigt die Komplexität der Berechnungen nur polynomiell (also nicht exponentiell) an, so wäre eine Matrix-Welt ein relativ einfach zu lösendes P-Problem und eine Matrix-Welt möglich. Steigt die Komplexität aber über-exponentiell an (NP-Problem), so wird eine Matrix-Simulation sehr schnell unwahrscheinlich.
Der Naturalist sagt nichts Abschließendes darüber, was in der Welt ist.
ThomasM
Beiträge: 5648
Registriert: Mo 20. Mai 2013, 19:43

Re: P ungleich NP? Erster Beweis gescheitert

Beitrag von ThomasM »

Nur drei Wochen nach der Publikation, hat Professor Blum den von ihm publizierten Beweis wieder zurückgezogen, es wurde ein Fehler entdeckt.
http://www.spektrum.de/news/der-angriff ... tent=heute

Noch ist nicht aller Tage Abend, vielleicht kann er seinen Beweis ja noch retten.
Wir werden sehen.
Gott würfelt nicht, meinte Einstein. Aber er irrte. Gott nutzt den Zufall - jeden Tag.
Antworten