P-NP-Problem gelöst? - Seite 2

Neue Frage »

Iridium Auf diesen Beitrag antworten »

Zitat:
Original von Mystic
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...


Wenn ich das richtig verstanden habe, beschreibt das letztendlich einen Algorithmus der mittels brute force einfach alle Möglichkeiten durchtestet und wegen P=NP dies dann eben auch in polynomialer Zeit schafft? An diese Möglichkeit habe ich nicht gedacht, sondern eher an einen "intelligenten" Algorithmus, der irgendwie auf direkterem Wege eine Lösung des jeweiligen Umkehrproblems (Primfaktorisierung, diskreter Logarithmus) liefert. Aber wenn es so ist, wie du schilderst, dann wäre wohl doch ziemlich bald nach einem Beweis von P=NP ein erhebliches Sicherheitsproblem gegeben (wobei das eigentlich ja schon besteht, solange man nicht beweisen kann, daß P=NP nicht gilt, d.h. quasi schon heute).
Mystic Auf diesen Beitrag antworten »

Zitat:
Original von Iridium
Wenn ich das richtig verstanden habe, beschreibt das letztendlich einen Algorithmus der mittels brute force einfach alle Möglichkeiten durchtestet und wegen P=NP dies dann eben auch in polynomialer Zeit schafft?

Nein, so war das definitiv nicht gemeint, denn das simple Durchprobieren aller Möglichkeiten hätte sicher ein exponentielles Laufzeitverhalten... Im Falle von P=NP müsste es aber dann einen anderen Algorithmus geben, der das in Polynomialzeit schafft...

Zitat:
Original von Iridium
Aber wenn es so ist, wie du schilderst, dann wäre wohl doch ziemlich bald nach einem Beweis von P=NP ein erhebliches Sicherheitsproblem gegeben (wobei das eigentlich ja schon besteht, solange man nicht beweisen kann, daß P=NP nicht gilt, d.h. quasi schon heute).

Nicht unbedingt, denn nochmals: Ein Polynomialzeitalgorithmus ist nicht automatisch gut bzw. praktikabel, wenngleich das in der Praxis dann doch meist zutrifft (lies dir dazu nochmals durch, was Manus und auch ich oben dazu geschrieben haben!) ... Meiner Meinung nach wäre es also theoretisch durchaus möglich, dass auch im Falle P=NP es dann zwar einen Polynomialzeitalgorithmus zum Entschlüsseln gibt, der aber letzlich für den Bereich des Eingabeparameters, wo man ihn einsetzen möchte, schlicht und einfach nicht praktikabel ist...
Iridium Auf diesen Beitrag antworten »

Zitat:
Original von Mystic
Meiner Meinung nach wäre es also theoretisch durchaus möglich, dass auch im Falle P=NP es dann zwar einen Polynomialzeitalgorithmus zum Entschlüsseln gibt, der aber letzlich für den Bereich des Eingabeparameters, wo man ihn einsetzen möchte, schlicht und einfach nicht praktikabel ist...


Du meinst, es könnte einen Polynomialzeitalgorithmus geben, der erst dann praktikabel wird, wenn z.B. die Schlüsselzahlen um extreme Größenordnungen größer sind als heute, wobei die heutigen Schlüsselzahlen aufgrund ihrer Größe gegen ein brute force Ausprobieren aller Möglichkeiten "sicher" sind (es gäbe dann einen intermediären Größenbereich der im Rahmen der technischen Rechenpower sicher wäre)? Hört sich mal wieder interessanter und komplizierter an, als man so zuerst meint.
Neue Frage »
Antworten »



Verwandte Themen