P-NP-Problem gelöst?

Neue Frage »

Vieta Auf diesen Beitrag antworten »
P-NP-Problem gelöst?
Folgender Artikel liest sich spannend:

http://www.zeit.de/wissen/2010-08/millen...weis-mathematik

Mfg Wink
Airblader Auf diesen Beitrag antworten »

Wow - das sind ja große Neuigkeiten, auch wenn natürlich alles noch durchgeschaut werden muss. geschockt

Juckt mich jetzt auch weniger, dass die etwas weniger befriedigende Lösung wäre .. immerhin wäre damit ein legendäres Rätsel gelöst!

Bin gespannt, was dabei rumkommt. Könnte aber wohl eine Weile dauern (außer man findet einen Fehler im Beweis).

air
giles Auf diesen Beitrag antworten »

Ist ja schon etwas älter die Meldung.
Wenn man bedenkt dass es jetzt schon ein paar falsche Beweise zu großen Problemen gegeben hat sollte man sich sowieso erst einmal zurückhalten mit der Euphorie smile .

Selbst wenn es denn nicht sein sollte, kann das zumindest neue Impulse geben.
P != NP ist aber weitaus weniger bedeutsam als andersrum (mehr als "etwas weniger"). Andersherum hätte sich eine ganz neue Welt der Algorithmen aufgetan... naja man kann nicht alles haben.
Vinyl Auf diesen Beitrag antworten »

Danke für den Hinweis. Interessanter Artikel. Mal sehen wie sich das weiterentwickelt.

LG Vinyl
Airblader Auf diesen Beitrag antworten »

Zitat:
Original von giles
Wenn man bedenkt dass es jetzt schon ein paar falsche Beweise zu großen Problemen gegeben hat sollte man sich sowieso erst einmal zurückhalten mit der Euphorie smile


Ja, das ist wohl die Kehrseite. Darum muss man noch abwarten.
Fermat wurde ja auch "oft" bewiesen, doch immer wieder stellte es sich als falsch heraus. Big Laugh

air
Airblader Auf diesen Beitrag antworten »

P.S.: Bin ich eigentlich der Einzige, der bei dem Threadtitel erst an einen Grafe-Nachfolger dachte? Big Laugh

air
 
 
Q-fLaDeN Auf diesen Beitrag antworten »

Das kann ich nicht sagen, aber ich dachte zuerst an einen pnp-Übergang Big Laugh
gonnabphd Auf diesen Beitrag antworten »

So wie ich das mitbekommen habe, scheinen sich die Probleme bei dem Beweis schon jetzt zu häufen...

Also kann man sich wohl wieder etwas entspannen...

Quelle:
P - NP

Und auch irgendwo weit unten ein paar Worte von

Terrence Tao

Wink
giles Auf diesen Beitrag antworten »

Hast da ja ein paar interessante Links gefunden, thx 4 share Wink
jester. Auf diesen Beitrag antworten »

Zitat:
Original von gonnabphd
Und auch irgendwo weit unten ein paar Worte von

Terrence Tao

Wink


Das klingt ja leider nicht so, als ob da in den nächsten Tagen etwas bahnbrechendes kommen würde. Eigentlich schade...
Airblader Auf diesen Beitrag antworten »

Ja, echt sehr schade!
Zugegebenermaßen frage ich mich auch, wie innerhalb von einigen Tagen etwas scheinbar so auseinandergenommen werden kann. Von einem etablierten Mathematiker geht man doch davon aus, dass er seine Arbeit - speziell wenn sie so bedeutend sein kann - hunderte Male überprüft (?)

air
gonnabphd Auf diesen Beitrag antworten »

Naja, ich schätze mal die anderen Leute (Tao) haben sich auch schon sehr sehr viele Gedanken über dieses Problem gemacht und kennen deshalb sicher auch viele Ansätze die bestimmt zu nichts führen können.
tmo Auf diesen Beitrag antworten »

Auch interesant: http://rjlipton.wordpress.com/2010/08/11/deolalikar-responds-to-issues-about-his-p%E2%89%A0np-proof/

Vor allem, wenn man sich selbst schonmal dabei erwischt hat, wenn man irgendwas bewiesen hat und einem dann plötzlich auffällt, dass dieser Beweis dummerweise auch eine Aussagen beweisen würde, die bekanntermaßen falsch ist unglücklich

Aber schön, dass es auch den Profis passiert, nur halt auf einem ganz anderen Niveau.
giles Auf diesen Beitrag antworten »

Zitat:
Original von tmo
Vor allem, wenn man sich selbst schonmal dabei erwischt hat, wenn man irgendwas bewiesen hat und einem dann plötzlich auffällt, dass dieser Beweis dummerweise auch eine Aussagen beweisen würde, die bekanntermaßen falsch ist unglücklich

Wer kennt das nicht Big Laugh

edit: Dort steht das Prinzip hätte keinen Namen. Wenn man damit auf etwas falsches kommt wäre es aber doch ein Fall von reductio ad absurdum. Nur halt dass man es statt auf Aussagen auf die Beweistechnik anwendet.
Airblader Auf diesen Beitrag antworten »

Das ging mir in LA letztes Semester irgendwie einige Male so ... dass eine Voraussetzung einfach nirgendwo mit eingeflossen ist. Allerdings ist dieses Argument manchmal auch sehr trügerisch, weil man u.U. nur nicht direkt sieht, dass die Voraussetzung irgendwo mit eingegangen ist. Big Laugh

air
Iorek Auf diesen Beitrag antworten »

Zitat:
Original von tmo
Aber schön, dass es auch den Profis passiert, nur halt auf einem ganz anderen Niveau.


Erinnert mich an meine vollständige Induktion, wo ich nebenbei gezeigt habe, dass ist Finger1
gonnabphd Auf diesen Beitrag antworten »

Newsflash:

Hmm, die Probleme mit dem Beweis werden nun handfester und scheinen ein grosses (unüberbrückbares?) Loch im Beweis zu hinterlassen...

Neuer Blogeintrag


Also können wir wohl alle unsere Arbeiten am P=NP? - Problem wieder aufnehmen. Big Laugh

Gruss. smile
Iorek Auf diesen Beitrag antworten »

Zitat:
Original von gonnabphd
Also können wir wohl alle unsere Arbeiten am P=NP? - Problem wieder aufnehmen. Big Laugh



Na, ich hoffe doch, dass die Post meinen Beweis dieses mal zustellt, ich hab den richtigen Beweis dafür doch schon vor 2 Wochen abgeschickt. böse

Immer das selbe mit den gelben Wagen...nie komme sie an Big Laugh
tmo Auf diesen Beitrag antworten »

Zitat:
Original von gonnabphd
Also können wir wohl alle unsere Arbeiten am P=NP? - Problem wieder aufnehmen. Big Laugh


Glück gehabt, hab schon gedacht, die Millionen geht mir durch die Lappen Big Laugh
Mystic Auf diesen Beitrag antworten »

Zitat:
Original von tmo
Glück gehabt, hab schon gedacht, die Millionen geht mir durch die Lappen Big Laugh

Ist leider nur eine Million, noch dazu in Dollar - also nicht wirklich wert, seine Zeit darauf zu verschwenden... Big Laugh
Airblader Auf diesen Beitrag antworten »

Man schaue sich nur den Perelman an, nicht wahr? Augenzwinkern

air
wogir Auf diesen Beitrag antworten »

Fühlt sich keiner berufen, einen Workshop zu erstellen um den Laien den Beweis zu erklären? Augenzwinkern
Q-fLaDeN Auf diesen Beitrag antworten »

Mach ich!
Airblader Auf diesen Beitrag antworten »

Wer verfolgt die Sache noch? Augenzwinkern
Ich fand folgendes sehr interessant:

http://rjlipton.wordpress.com/2010/08/12...lalikars-proof/

Nicht den Artikel, sondern die Kommentare. Jetzt kochen stellenweise ja echt Emotionen hoch und auch Stimmen werden laut, der Versuch sei purer Wahnsinn gewesen etc.

air
Iridium Auf diesen Beitrag antworten »

Zitat:
Original von Airblader
Nicht den Artikel, sondern die Kommentare. Jetzt kochen stellenweise ja echt Emotionen hoch und auch Stimmen werden laut, der Versuch sei purer Wahnsinn gewesen etc.


Schon die Kommentare sind irgendwie furchteinflößend. Und zwar nicht mal die, welche den Autor irgendwie persönlich madig machen wollen, sondern die rein fachlichen.

Ich persönlich verstehe zu wenig von der ganzen Materie, aber in meinem Wissenschaftlerleben habe ich immer sehr viel Sympathien übrig gehabt (und hab sie noch) für die Wahnsinnigeren unter den Wahnsinnigen (welcher ernsthafte Mathematiker ist schon normal?). In vielen Fällen sind es Spinner, ja, oft genug sind die Beiträge dieser Leute nicht so besonders, wie diese sie selbst einschätzen, aber hin und wieder leisten diese Leute wirklich Großes, gerade weil sie sich vielleicht überschätzen, gerade weil sie keinen Respekt vor großen Problemen haben, gerade weil sie eh schon so wenig angepasst sind, als daß sie Rücksicht nehmen müssen, und gerade weil ihnen Anerkennung weniger bedeutet, als die eigentliche Arbeit und ihr Inhalt. Wer 100 Seiten schreibt und ernsthaft den Mumm hat, sich damit in die Höhle des Löwen zu trauen (bevölkert von mediocren Mathematiker, die nur darauf warten jemanden anzufallen, der Schwächen offenbart), dem gebührt schon dafür Respekt. Immerhin ein Versuch, immerhin eine eigene Gedankenleistung...selbst wenn sich am Ende (wie es vielleicht jetzt schon ausschaut) herausstellt, daß es doch kein hieb- und stichfester Beweis ist.
Airblader Auf diesen Beitrag antworten »

Ich glaube diese Art von Respekt haben die meisten Leute dort und ebenso sind sich die meisten ja einig, dass auch ein falscher Beweis viel bringen kann.
Von der Materie verstehe ich ja auch nichts, aber ein Kritikpunkt, den ich gelesen habe und den man verstehen kann, war der, dass der Beweis anscheinend damit arbeitet, dass sich alle P-Probleme mit einer bestimmten Eigenschaft 'Q' beschreiben lassen, die der Autor verwendet .. und dies hält einer eben für so absurd, dass er es zum Ausdruck bringt. Der Vorwurf ist also, dass mit bereits viel zu simplen Methoden geschossen wird, aus denen gar nicht die Komplexität der Aussage entspringen kann.
Beurteilen kann ich das aber auch nicht.

air
Mystic Auf diesen Beitrag antworten »

@Iridium

Ich sehe das jetzt nicht ganz so positiv, was vielleicht auch damit zusammenhängt, dass zu meinen Kernbereichen auch die Zahlentheorie gehört, wo sich ja bekanntlich besonders viele "Hobbymathematiker" tummeln, die dann mit ihren "Beweisen" von berühmten mathematischen Vermutungen oft ganz schön "lästig" sein können... Aber das sind jetzt nur meine ganz persönlichen Erfahrungen, was aber um Gottes willen nicht heißt. dass ich im gegenständlichen Fall Deolalikar auf eine Stufe mit diesen Hobbymathematikern stelle, dazu ist sein Paper doch zu seriös...

Tatsächlich sind aber rein objektiv in der Geschichte der Mathematik Fälle, wo "mathematische Außenseiter", d.h., nicht der arrivierten Zunft angehörende mathematisch Tätige, essentielle Beiträge geliefert haben, sehr selten, wenngleich nicht ganz ausgeschlossen... Der spektakulärste Fall dieser Art ist wohl der von Kurt Heegner, eigentlich Ingenieur für Funktechnik, der als erster und im wesentlichen korrekt eine berühmte Vermutung von Gauß bezüglich imaginär quadratischer Zahlkörper mit Klassenzahl 1 bewiesen hat...

Aber das sind, wie gesagt, Ausnahmen, welche eigentlich nur die Regel bestätigen... In sehr vielen Fällen steckt einfach Unwissen über die wahren Schwierigkeiten des Problems dahinter oft gepaart mit der doch einigermaßen überheblichen Einstellung, dass alle welche sich bislang damit beschäftigt haben, die eigene "geniale" Lösung ganz einfach "übersehen" haben...
giles Auf diesen Beitrag antworten »

Habt ihr euch mal das Paper angesehen?
Sehr viel Rekapitulation anderer Ergebnisse, wenig mathematische Struktur. Die Essenz des Papers hätte man auch auf 10 einfach zu verifizierende Seiten mit Lemma-Lemma-Theorem Struktur kondensieren können.
Ich sehe keinen Grund einen Beweis den man selbst erstellt hat nicht in so einer offenen Weise zu präsentieren, es sei denn man ist sich selbst unsicher darüber und möchte das verdecken. Genau da kommt auch mmn. der meiste Unmut der Kritiker her.
Shortstop Auf diesen Beitrag antworten »

Ich denke der Grund dafür, dass das Thema auf einmal so hitzig diskutiert wird liegt unter anderem auch in der wirtschaftlichen Bedeutung des Problems.

Immerhin ist dies nicht ganz unwichtig bzgl. der Zukunft der Verschlüsselung wie RSA oder ECC. Man kann nur hoffen, dass wirklich P!=NP ist.
Airblader Auf diesen Beitrag antworten »

Wobei P != NP für klassische Problemstellungen natürlich auch zur Folge hätte, dass diese womöglich tatsächlich so schlecht lösbar sind, wie man momentan denkt.

Es hat eben alles seine Vor- und Nachteile. Verschlüsselungstechnologie ist vielleicht aber mit das Wichtigste, ergo wäre P != NP wohl echt wünschenswert.

@ giles

Ja, ich habe es mir mal angeschaut und hatte genau diesen Eindruck. Ich habe vergeblich nach "Symbolen" gesucht und kaum welche gefunden. Muss zwar erstmal nichts heißen, aber bei einem so formalen Problem war ich davon ausgegangen, dass ein bisschen Text eben nicht genügt.
Allerdings verstehe ich von der Materie ja nichts, darum habe ich es mir auch nicht näher angeschaut als dieses "Überfliegen".

air
Iridium Auf diesen Beitrag antworten »

Zitat:
Original von Mystic
@Iridium

Ich sehe das jetzt nicht ganz so positiv, was vielleicht auch damit zusammenhängt, dass zu meinen Kernbereichen auch die Zahlentheorie gehört, wo sich ja bekanntlich besonders viele "Hobbymathematiker" tummeln, die dann mit ihren "Beweisen" von berühmten mathematischen Vermutungen oft ganz schön "lästig" sein können...


Ja, davon hört man immer wieder. Ich kann das schwer einschätzen, wie lästig sowas werden kann, weil man als Chemiker selten von Laien belästigt wird, die einem irgendein Problem lösen wollen und nachher in ihrer Wohnküche synthetisieren smile . Außerdem ist ja die Antriebskraft eine andere. Ewiger Ruhm für eine geniale mathematische Idee. Und je einfacher der Beweis nachher ist, desto größer ist der Ruhm, weil ihn ja alle anderen Mathematiker übersehen haben. Und je geringer die eigenen Fähigkeiten desto noch mal größer ist der Ruhm, weil die Differenz zu einem echten Mathematiker entsprechend groß ist. Na ja, und man braucht wohl eine gewisse unerschütterliche Persönlichkeitsstruktur.

Zitat:
Original von Mystic
Tatsächlich sind aber rein objektiv in der Geschichte der Mathematik Fälle, wo "mathematische Außenseiter", d.h., nicht der arrivierten Zunft angehörende mathematisch Tätige, essentielle Beiträge geliefert haben, sehr selten, wenngleich nicht ganz ausgeschlossen... Der spektakulärste Fall dieser Art ist wohl der von Kurt Heegner, eigentlich Ingenieur für Funktechnik, der als erster und im wesentlichen korrekt eine berühmte Vermutung von Gauß bezüglich imaginär quadratischer Zahlkörper mit Klassenzahl 1 bewiesen hat...


Mir fallen noch Robert Ammann ein und irgendwie auch Ramanujan, denn der hatte ja auch keine formale mathematische Ausbildung, sondern hat seine Resultate gerüchteweise von einer hinduistischen Gottheit eingesagt bekommen, was man direkt glauben will, wenn man manche Formeln sieht.

Was P ?= NP angeht...ich weiß nicht, ob es nicht nachher für die Menschheit besser wäre, wenn sich herausstellen würde, daß es effektive Algorithmen zur Umkehrung der Verschlüsselungsmethoden gäbe. Ok, man könnte vermutlich nicht mehr so bequem online-banking betreiben...aber dafür gäbe es gute Möglichkeiten die Arbeiten von Geheimdiensten und anderem Gesindel erheblich zu erschweren, sprich zu nerven, wo man kann.
Shortstop Auf diesen Beitrag antworten »

Zitat:
Original von Iridium
aber dafür gäbe es gute Möglichkeiten die Arbeiten von Geheimdiensten und anderem Gesindel erheblich zu erschweren, sprich zu nerven, wo man kann.


Das wäre die zweite Seite der Medaille. Ich glaube das Ausmaß eines möglichen Beweises von P=NP ist garnicht abzusehen. Allerdings halte ich es wirklich für wahrscheinlicher, dass dies nicht der Fall sein wird...

Trotzdem ist die Mathematik ja immer wieder für Überraschungen gut. Grade deswegen finde ich sie so spannend smile

Lassen wir uns überraschen, wie es mit dieser Geschichte weitergeht...

Mein Tip: Den Beweis gibts innerhalb der nächsten 2 Jahre.
Iridium Auf diesen Beitrag antworten »

Zitat:
Original von kvnb
Das wäre die zweite Seite der Medaille. Ich glaube das Ausmaß eines möglichen Beweises von P=NP ist garnicht abzusehen. Allerdings halte ich es wirklich für wahrscheinlicher, dass dies nicht der Fall sein wird...

[...]

Mein Tip: Den Beweis gibts innerhalb der nächsten 2 Jahre.


Ich erinnere mich dunkel, daß es vor einiger Zeit (Anfang des Jahres?) in Spektrum der Wissenschaft zu lesen war, daß es andere Leute gibt, die gerade vielversprechende Arbeiten in diese Richtung machen.

Im übrigen würde, soweit ich das verstehe, selbst ein Beweis P=NP ja nicht sofort zum Weltuntergang führen...was Verschlüsselung betrifft. Denn bisher hat noch niemand einen schnellen Algorithmus gefunden und warum sollte sich das so schnell ändern? Man weiß dann nur eben, daß es einen geben muß...und natürlich gäbe es dann eine ganz andere Motivation einen zu finden, aber das kann gut und gerne Jahrhunderte dauern, oder irre ich mich da?
Airblader Auf diesen Beitrag antworten »

Das ist - soweit ich weiß - zwar korrekt, aber es erzeugt doch ein eher mulmiges Gefühl im Magen, macht es den Untergang von Verschlüsselungsmethoden doch wesentlich greifbarer.
Schöner wäre es, eine Methode zu haben, von der man beweisen kann, dass sie in gewisser Hinsicht "unknackbar" ist. Das wäre dann ja aber ausgeschlossen.

air
Mystic Auf diesen Beitrag antworten »

Zitat:
Original von Iridium
Im übrigen würde, soweit ich das verstehe, selbst ein Beweis P=NP ja nicht sofort zum Weltuntergang führen...was Verschlüsselung betrifft. Denn bisher hat noch niemand einen schnellen Algorithmus gefunden und warum sollte sich das so schnell ändern? Man weiß dann nur eben, daß es einen geben muß...und natürlich gäbe es dann eine ganz andere Motivation einen zu finden, aber das kann gut und gerne Jahrhunderte dauern, oder irre ich mich da?

Ja, ich denke, da irrst du dich... Zumindestens intepretiere ich das, was hier (im Abschnitt "Zur Lösung des Problems") über den Fall P=NP steht so, dass man auch im Falle eines nichtkonstruktiven Beweises der Gleichheit P =NP dann heute schon NP-vollständige Probleme kennt, welche dann automatisch in P liegen würden, was dann also insgesamt einen konstruktiven Beweis ergibt...
Airblader Auf diesen Beitrag antworten »

@ Mystic

Schießt deine Antwort nicht etwas an Iridiums Frage vorbei?
Ihm ging es ja nicht darum, dass man prinzipiell zu irgendwelchen problematischen Situationen noch keinen schnellen Algorithmus gefunden hätte. Es mag ja sein, dass man den in manchen Fällen dann bereits konstruieren kann. Iridium ging es ja mehr um ganz konkrete Problemstellungen wie in der Kryptologie. Auf wikipedia steht jedenfalls nicht, dass unter den Problemen, die man dann konstruktiv effizient lösen kann, auch solche Probleme fallen (aber es wird auch nicht ausgeschlossen). Augenzwinkern

air
Iridium Auf diesen Beitrag antworten »

Zitat:
Original von Mystic
Ja, ich denke, da irrst du dich... Zumindestens intepretiere ich das, was hier (im Abschnitt "Zur Lösung des Problems") über den Fall P=NP steht so, dass man auch im Falle eines nichtkonstruktiven Beweises der Gleichheit P =NP dann heute schon NP-vollständige Probleme kennt, welche dann automatisch in P liegen würden, was dann also insgesamt einen konstruktiven Beweis ergibt...


Ja, offenbar gibt es schon Algorithmen für NP-vollständige Probleme, die man bei einem entsprechenden Beweis anwenden könnte, aber fallen darunter auch Kryptographieprobleme, die vermutlich die bedeutendste praktische Anwendung darstellen?

Weiter unten in dem Wikipedia-Artikel (unter "Praktische Relevanz") steht zumindest folgendes:

"Sehr viele, auch praktisch relevante Probleme, sind NP-vollständig. Die Lösung des Problems könnte daher von großer Bedeutung sein. Der Beweis von P=NP würde bedeuten, dass für Probleme der bisherigen Klasse NP Algorithmen existieren, die eine Lösung in – wesentlich schnellerer – Polynomialzeit generieren können. Da es jedoch in den vergangenen Jahrhunderten noch nicht gelungen ist, auch nur einen einzigen dieser Algorithmen zu finden, wird in der Fachwelt angezweifelt, dass diese Algorithmen überhaupt existieren."

Vielleicht widerspricht sich hier die Wikipedia, ich kann das nicht beurteilen. Aber die Schlußfolgerung, weil man jahrhundertelang etwas nicht findet, existiere es nicht, ist ja nun auch nicht besonders mathematisch. Einen Tag vor Wiles hat sicher auch kaum jemand darauf gehofft, noch zu leben, wenn Fermat bewiesen wird und ich erinnere mich auch noch an ein anderes Beispiel (irgendeins mit den Primzahlen), wo man glaubte dies und jenes gäbe es nicht, bis jemand das Gegenbeispiel per Mail verschickt hat. Ich fände es auf jedenfall spannender, wenn P=NP bewiesen werden würde und man eben nicht wüsste, ob nicht schon irgendjemand einen passenden Algorithmus in der Tasche hat (denn bei der Bedeutung dieses Algorithmusses muß man ihn ja nicht unbedingt veröffentlichen! Vielleicht hat irgendein NSA-Mathematiker P=NP schon bewiesen, aber aus Gründen der nationalen Sicherheit wird das unter Verschluß gehalten...und der Mathematiker hatte bedauerlicherweise am Tag darauf einen tödlichen Autounfall Teufel ).
Manus Auf diesen Beitrag antworten »

Hinzu kommt ja, dass ein Polynomialzeit-Algorithmus ja möglicherweise auf den ersten Zahlen tatsächlich langsamer ist als die bekannten, nicht-polynomialen Algorithmen; einfach aus dem Grund, dass das entsprechende Polynom einen extrem hohen Grad hat.

Beispiel wäre hier "PRIMES is in P" bzw. der AKS-Primzahltest. Der ist zwar polynomial, aber trotzdem grausam langsam im eher "niedrigen" Bereich. (Im tatsächlich niedrigen Bereich wird er sogar von Trial-Division geschlagen.) So ein Algorithmus spielt seine Stärke im Vergleich zu anderen Algorithmen halt erst aus, wenn die Eingabegröße wahnsinnig groß ist.
Mystic Auf diesen Beitrag antworten »

Zitat:
Original von Airblader
Iridium ging es ja mehr um ganz konkrete Problemstellungen wie in der Kryptologie. Auf wikipedia steht jedenfalls nicht, dass unter den Problemen, die man dann konstruktiv effizient lösen kann, auch solche Probleme fallen (aber es wird auch nicht ausgeschlossen). Augenzwinkern

Doch, steht m.E. schon in dem von mir verlinkten Wikipedia-Artikel, nämlich unter der Überschrift "Praktische Relevanz"

Zitat:

Ein NP-Algorithmus kann ein beliebiges asymmetrisches Kryptosystem brechen, indem er den geheimen Schlüssel „errät“ und mit dem Verfahren, das der eigentliche Empfänger der Nachricht benutzen würde, effizient entschlüsseln bzw. verifizieren.

Ich hätte das allerdings etwas anders formuliert, nämlich so: Man richtet einen Suchbaum ein, dessen einzelne Pfade alle Möglichkeiten repräsentieren, wie die geheimen Parameter, welche man für die Entschlüsselung braucht, aussehen könnten... Jeder einzelne Pfad kann dann in Polynomialzeit durchlaufen werden (andernfalls hätte auch der rechtmäßige Empfanger, der ja auch "seinen" Pfad durchlaufen muss, ein Problem!), um aber alle Pfade auf einmal zu durchlaufen, würde man eine nichtdeterministische Turingmaschine benötigen... Wir haben somit ein klassisches NP-Problem vorliegen, das im Falle von P=NP natürlich dann auch in P liegen würde...

@Iridium

Ich habe dem sehr guten Kommentar von Manus im Grunde nichts hinzuzufügen... Es wir leider oft vergessen, dass die Tatsache, dass ein Problem in P liegt, zunächst einmal nur heißt, dass es "asymptotisch", sprich für "große" Werte des relevanten Eingabeparameters, einen Algorithmus dafür gibt, der schnell ist, genauer schneller, als für jedes Problem mit nur exponentieller Laufzeit... Der Teufel steckt oft im Detail, nämlich im Exponenten k bei der Polynomialzeitabschätzung , sowie auch in der Konstanten, welche sich hinter der O-Notation versteckt und oft für einen gewaltigen "overhead" sorgt, der sich dann bei "kleinen" Werten des Eingabeparameters n massiv bemerkbar macht... Und ja, der AKS-Primzahltest ist ein wunderbares Beispiel in dieser Hinsicht...
Airblader Auf diesen Beitrag antworten »

@ Mystic

Hups. Hast natürlich recht. Freude

air
Neue Frage »
Antworten »



Verwandte Themen