P != NP gelöst ?

[blablub1212]

dann gibts wieder neue probleme ... denn aus den beweisen lassen sich neue theorien erstellen die wieder bewiesen werden müssen etc pp

 

[Hilbertraum]

Finde das Ganze jedenfalls generell sehr spannend, mal schaun was die Reviewer sagen

 

[Christock]

Hätte ich gewusst, dass es dafür eine Millionen US-Dollar gibt...

Im Ernst: Ich finde es sehr faszinierend, wenn für etwas, von dem das Gros der Wissenschaftler bereits ausgegangen ist, ein formal-logischer Beweis erbracht wird. Der Nutzen ist dabei Erkenntnis, die sich dabei auf der elementarsten propositionalen Form des Denkens gründet und auf diese Weise die größtmögliche Form intersubjektiver Sicherheit mit sich führt.

 

[Stefan_Sch]

Das ist eine weithin anerkannte und in der meisten Fällen auch ausreichende Erklärung, allerdings mit einem kleinen Caveat: NP-Probleme könnten irgendwann durchaus auch in polynomieller Zeit gelöst werden, allerdings eben nicht von unseren heute realisierbaren Rechenmaschinen.
Was mit Deolalikars Beweis jetzt auch bewiesen wäre, ist, dass solche Rechenmaschinen (als Beispiel: Quantencomputer, möglicherweise) tatsächlich besser im Lösen von NP-Problemen wären als unsere heutigen deterministischen Rechner. Ich bin da allerdings noch sehr vorsichtig und warte die Peer Reviews ab.

Im Grunde ist das genau der Unterschied zwischen P und NP. Probleme, die nachweislich in P liegen, sind mit deterministischen Maschinen in höchstens der Zeit-Komplexität eines Polynoms endlichen Grades berechenbar. Für NP kann dies nur auf nicht-deterministisch arbeitenden Maschinen funktionieren (dafür steht das N in NP).

Noch ist nichts bewiesen, dazu bedarf es zunächst einmal einer sorgfältigen Prüfung der Arbeit.

Unter Mathematikern und Informatikern wird schon lange vermutet das beide Komplexitätsklassen sich unterscheiden, es fehlt bisher der mathematische einwandfreie Beweis. Zumal man keinen polynomiell zeitbeschränkten Algorithmus für NP-vollständige Probleme auf einer deterministischen Rechenmaschine in der Praxis finden konnte. Die grundlegende Frage lautet eben, ob sich jedes Problem, das sich nichtdeterministisch in polynomieller Zeit lösen lässt, auch deterministisch in Polynomalzeit lösen.

Falls der Beweis gelingt hätte das nicht so weitreichende Konsequenzen, weil man aus der Praxis nunmal schon lange vermutet hat das N ≠ NP ist. Der Beweis N = NP wäre dagegen viel folgenschwerer und damit ist nicht einfach nur das Faktorisierungsproblem für ganze Zahlen, bei der der Beweis der NP-Vollständigkeit fehlt, in asymmetrischen Verschlüsselungsalgorithmen gemeint. Das betrifft alle unsere Lebensbereiche.

Nichtdeterministische Turingmaschinen gibt es bekanntlich nicht und wird es wahrscheinlich auch niemals geben. Eine NTM ist vielmehr ein gedankliches Konzept mit einem geheimnisvollen Orakel. Die Frage nach Determinismus ist ohnehin in der Natur noch weitestgehend unbeantwortet.

 

[Haudrauff]

Hätte ich gewusst, dass es dafür eine Millionen US-Dollar gibt...

War dies ein von den unlängst ausgeschriebenen 7 ungelösten Rätseln der Mathematik?
Pro Rätel gibts da 1 Million Dollari.
Ich dachte ich hab da mal was davon gehört...

PS:

Kurz und sehr vereinfacht:
.....

Hä?

 

[kaikuwe]

War dies ein von den unlängst ausgeschriebenen 7 ungelösten Rätseln der Mathematik?
Pro Rätel gibts da 1 Million Dollari.
Ich dachte ich hab da mal was davon gehört...

PS:

Hä?

Jop, unlängst ist aber relativ und ich meine ursprünglich waren es sogar mal zehn!

Naja, viel einfacher geht es leider nicht!

 

[davediehose]

Falls der Beweis gelingt hätte das nicht so weitreichende Konsequenzen, weil man aus der Praxis nunmal schon lange vermutet hat das N ≠ NP ist. Der Beweis N = NP wäre dagegen viel folgenschwerer und damit ist nicht einfach nur das Faktorisierungsproblem für ganze Zahlen, bei der der Beweis der NP-Vollständigkeit fehlt, in asymmetrischen Verschlüsselungsalgorithmen gemeint. Das betrifft alle unsere Lebensbereiche.

Es hätte sogar beides schwerwiegende Konsequenzen, in beiden Fällen positiv wie negativ. Der vorgeschlagene Fall von P != NP würde nach sich ziehen, dass NP-harte Probleme weiterhin und für alle Zeiten - außer mit Nichtdeterminismen - nur sehr schwer zu lösen wären. Das würde einerseits - auf Grund der Schwierigkeit der Primfaktorzerlegung - die zur Zeit benutzten Kryptoverfahren wie RSA (Schlüsselberechnung mit Hilfe Eulerscher Phi-Funktion, Teilerfremdheit wird ausgenutzt) auf lange Zeit hin sichern, zumindest solange keine Sicherheitslücken entdeckt werden. Andere Probleme, die man aber gerne schnell gelöst haben will, wären dann allerdings auch für alle Zeiten schwer zu lösen.

Wäre P = NP, wären zwar alle asymmetrischen Kryptoverfahren über kurz oder lang in Gefahr, es hieße aber auch, dass es effiziente Algorithmen für überaus wichtige, aber sehr (Zeit-)komplexe Probleme wie Traveling Salesman oder das Rucksackproblem geben muss. Bisher wurden keine gefunden, was an sich schon eher für P != NP spricht, das ist richtig. Allerdings ist es schon oft vorgekommen, dass sich über hunderte von Jahren Leute zwar Gedanken gemacht haben, aber entscheidende Aspekte erst viel später verstanden wurden, von daher sollte man erstmal nichts ausschließen.

Insgesamt ist P != NP die "konservative", aber auch nicht komplett angenehme Version, wohingegen P = NP revolutionär wäre, im positiven wie im negativen Sinne. Wenn man es jetzt genau wüsste, wäre es so oder so aber von Vorteil.