P != NP gelöst ?

[Hilbertraum]

Hat sich das mal jemand durchgelesen:
http://www.win.tue.nl/~gwoegi/P-versus-NP/Deolalikar.pdf

Ist es wirklich ersthaft das, wonach es aussieht ?

 

[elh4jj4j]

Ich bin gespannt, ob dir das jemand beantworten kann.^^

PS: Er wäre der Erste.

 

[kuddlmuddl]

Naja ob der Beweis tatsächlich fehlerfrei ist wird sich nicht von heute auf morgen zeigen.. aber es scheint ernst genommen zu werden

http://www.heise.de/newsticker/meldung/P-NP-moeglicherweise-bewiesen-1052857.html

edit:
http://www.heise.de/newsticker/fore...her-skeptisch/forum-183950/msg-18958503/read/
bzw.
http://scottaaronson.com/blog/?p=456

 

[Hilbertraum]

Sehr krass, wen dem so wäre, dann ist der 6.8.2010 ein denkwürdiger Tag für jeden Informatiker und Mathematiker. Wäre beruhigend zu wissen, dass viele der aktuell benutzten Verschlüsselungen sicher sind.

Bin sehr sehr gespannt auf die Auswertung des Beweises!

 

[jodd]

Und was bringt das im praktischen Leben?

 

[Haudrauff]

Die sollen lieber mal Pi ausrechen. Das würde zumindest jeder verstehen.
Was ist den eigentlich P und NP?

Problem und No Problem?

 

[Proxy One]

Und was bringt das im praktischen Leben?

Grundlagenforschung, vor 60 Jahren wusste auch keiner mit nem Transistor was anzufangen.

 

[Mr.Mkay]

Das wollte ich auch gerade fragen.
Geht es grob in die Richtung, dass es für zukünftige Quantenprozessoren von bedeutung sein kann? irgendwie hab ich da grob was in die Richtung rauslesen können bei Heise, zumindest um "zufällige" Berechnungsweisen und das klingt doch sehr nach Quantenmechanik.

Greetz

 

[blablub1212]

"Der praktische Nutzen ist durchaus vorhanden. P=NP würde bedeuten,
dass zu jedem Problem in NP ein Algorithmus existiert, der das
Problem in Polynomialzeit löst. Und das wäre eine Katastrophe, denn
die asymmetrischen Verschlüsselungsverfahren, die heute verwendet
werden, basieren darauf, dass für das Problem der Primfaktorzerlegung
(welches in NP liegt) kein effizienter Algorithmus existiert. Falls
P=NP müsste man jederzeit damit rechnen, dass ein Algorithmus
gefunden wird, der asymmetrische Verschlüsselungen mit langem
Schlüssel effizient knacken kann. P!=NP bedeutet umgekehrt, dass die
heutigen Verfahren mit hinreichend langen Schlüsseln langfristig
sicher sind."

das beschreibt den nutzen ganz gut und verständlich ...

 

[Hilbertraum]

Und was bringt das im praktischen Leben?

Gewissheit Nein, mal im Ernst, ich finde es einfach interessant. Praktische Auswirkungen hat dies kaum, bzw nicht direkt. Verschlüsselungen von denen man bisher nur vermutete, dass diese nicht Effizient Knackbar sind, sind dies nun mit absoluter Sicherheit. Ressourcen (Brain-Power) die momentan von tausenden Menschen dazu verwendet werden, dieses Problem zu lösen und vielleicht einen effizienten Algortihmus für alle NP Probleme zu finden, ( Was wiederrum praktischen Nutzen hätte ) können diese nun sinnvoller nutzen, da dies ja dann nicht möglich wäre

Es ist eben eines der bedeutensten Probleme in der Mathematik, und mit weitem Abstand des beudetenste Problem in der Informatik. Die Grenze des machbaren

 

[jodd]

Sicher, das ganze ist für *Ottonormalbrürger* aber viel zu abstrakt um damit etwas anfangen zu können. Der kann auch mit der 5 Billionsten Dezimalstelle von PI nichts anfangen, der wird sich eher fragen: Haben die nichts besseres zu tun, haben wir sonst keine Probleme.

 

[>|Sh4d0w|<]

Natürlich werde ich mir den 100 Seitigen Beweis sorgfältig durchlesen. Ich weiß, dass es ein bisschen kompliziert sein wird, aber dafür nehme ich mir auch ruhig die Zeit. Denn jeder weiß wie wichtig das fürs Leben eines Fachinformatikers ist. Schon alleine nach der Einleitung ist mir klar, dass es kein einfacher Stoff sein wird und ich kann mir sehr gut vorstellen, dass es einige Zeit braucht, bis dieser Beweis akzeptiert ist.

Ich bin jetzt froh, dass diese Frage endlich geklärt ist und ich jetzt endlich ruhig schlafen kann.

 

[kaikuwe]

Es ist "noch" nicht bewiesen, dass die Primfaktorzerlegung NP vollständig ist (oder korrigiert mich). Somit nutzt der Beweis, was Verschlüsselungen angeht noch nichts.

Edit:
Aber ich bin auch schon länger aus dem Thema raus. Obwohl ich mir den Beweis sicherlich auch mal genauer durchlesen werd.

 

[Hilbertraum]

Nein, bezüglich der Primfaktorzerlegung hast du recht ... Soweit ich weiss gibt es andere Verschlüsselungen ( als z.B. RSA), die bewiesen NP sind und dann auch bewiesen sicher wären. Meine letzte Krypt Vorlesung ist leider schon was her... Vielleicht kann mir diesbezüglich jemand auf die Sprünge helfen...

 

[kaikuwe]

Das kann sein - ich muss gestehen, was Verschlüsselung angeht habe ich nicht wirklich viel AHnung.

Einen direkten Nutzen gibt es für den Herrn, der den Beweis geschrieben hat, sofern er als korrekt akzeptiert wird. Denn das Problem ist vom Clay Mathematical Institute als eines der noch sieben größten mathematischen, ungelösten Probleme ausgeschrieben. Und die Lösung der Probleme ist mit je 1Mio. US-Dollar dotiert.

 

[nicoc]

... als eines der noch sieben größten mathematischen, ungelösten Probleme ausgeschrieben. Und die Lösung der Probleme ist mit je 1Mio. US-Dollar dotiert.

[Zynismus]
... und dann kommt das Paradies? Weil dann wäre ja alles geklärt. Z. B. wie Liebe funktioniert, wie und warum der Mensch zum Alkoholiker wird... Prima.
EDIT: viel wichtiger: uns wird die Unendlichkeit erklärt.

 

[Hilbertraum]

Wenn der Beweis korrekt ist dann hat der Mann es sich sowas von verdient ...
Steht noch der Beweis aus, ob Gott existiert oder nicht ..

 

[kaikuwe]

Die sollen lieber mal Pi ausrechen. Das würde zumindest jeder verstehen.
Was ist den eigentlich P und NP?

Problem und No Problem?

Kurz und sehr vereinfacht:
P und NP sind Klassen die Algorithmen umfassen. Mengen wenn man es so nimmt. P ist eine Teilmenge von NP.

P umfasst die Klasse von Algorithmen die sich in polynomieller Rechenzeit, gemessen an der Eingabemenge n lösen lassen.

NP umfasst die Klasse der Algorithmen die sich in nicht polynomieller Zeit, gemessen an der Eingabemenge n lösen lassen.

Teilmenge, da sich Algorithmen, die sich in polynomieller Zeit lösen lassen, natürlich auch in nicht polynomieller Zeit lösen lassen.

Noch einfacher, es geht um die Berechenbarkeit von Problemstellungen! Man könnte jetzt denken, da geht es um die wildesten und kompliziertesten Problemstellungen. Das ist oft aber gar nicht so, da selbst scheinbar sehr einfach Probleme in NP fallen.
Beispiel: Graphenfärbeproblem
Man hat Knoten und Kanten in einem Graphen, Knoten die verbunden sind durch eine Kante heißen benachbart. Das Graphenfärbeproblem ist nun, dass man die Knoten einfärben will, wobei benachbarte Knoten nicht die gleiche Farbe haben dürfen. Ziel möglichst wenige Farben zu nutzen! Klingt sehr einfach fällt aber in NP.

Das wollte ich auch gerade fragen.
Geht es grob in die Richtung, dass es für zukünftige Quantenprozessoren von bedeutung sein kann? irgendwie hab ich da grob was in die Richtung rauslesen können bei Heise, zumindest um "zufällige" Berechnungsweisen und das klingt doch sehr nach Quantenmechanik.

Greetz

Jein, Quantencomputer könnten die Ideen dahinter relativ überflüssig machen. Da alle Annahmen hier auf deterministischen Maschinen (Turingmaschinen), wie die heutigen Computer es sind, beruhen.


So, das soll reichen.

PS: Korrigiert mich wenn ich falsch liege, bin wie weiter oben gesagt, scho etwas raus aus dem Thema.

 

[davediehose]

"Der praktische Nutzen ist durchaus vorhanden. P=NP würde bedeuten,
dass zu jedem Problem in NP ein Algorithmus existiert, der das
Problem in Polynomialzeit löst. Und das wäre eine Katastrophe, denn
die asymmetrischen Verschlüsselungsverfahren, die heute verwendet
werden, basieren darauf, dass für das Problem der Primfaktorzerlegung
(welches in NP liegt) kein effizienter Algorithmus existiert.

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).


Edit:

NP umfasst die Klasse der Algorithmen die sich in nicht polynomieller Zeit, gemessen an der Eingabemenge n lösen lassen.

Auch hier: Nicht ganz. NP steht für nichtdeterministisch polynomiell, was besagt, dass man das Problem (dem Beweis entsprechend: nur!!!) mit einem nichtdeterministischen Vorgehen in Polynomialzeit lösen kann. Das bedeutet einfach gesagt, dass die rechnende Maschine nicht komplett vorhersehbar agiert und sich von einem zum nächsten definierten Zustand bewegt, sondern beim Ablaufen eines Algorithmus den nächsten Schritt (wohl nicht ganz zufällig) "errät".

 

[kaikuwe]

[Zynismus]
... und dann kommt das Paradies? Weil dann wäre ja alles geklärt. Z. B. wie Liebe funktioniert, wie und warum der Mensch zum Alkoholiker wird... Prima.
EDIT: viel wichtiger: uns wird die Unendlichkeit erklärt.

Hmm, gute Frage. Mail mal an die Jungs vom Institut was dann kommt. Die Antwort würde mich interessieren!

Ich denke es geht eine rote Rundumleuchte an, es kommt laute Musik, lauter nackte Frauen fangen zu tanzen an und Konfetti kommt aus der Decke. Und "Hey, wo kommt der Alkohol her?"