...erörter das mal bitte für Inkompetente, ich finde das dubios, verstehe aber leider so gut wie nichts davon. Doch es erfüllt mich mit Schrecken.

HAHAHA.
Oh nein, ich muss diesen Thread sofort weiterverlinken. xD Den Links widme ich mich gleich, morgen oder sonstwann mal, aus purem Interesse.

Original von Ark
Sollte sich jedoch herausstellen, dass P = NP ist, dürfte die Apokalypse mehr oder weniger augenblicklich eintreten.

Ark

Das stimmt so nicht.
Es würde lediglich beweisen, dass man mit dem richtigen Algorhythmus in relativ (!) kurzer Zeit die zwei Primzahlen bestimmen kann, wenn man ihr Produkt kennt.
Aber eben: Mit dem richtigen Algorhythmus! Und bloss weil bewiesen wurde, dass es ihn gibt, wissen wir noch nicht wie wir ihn finden.

Es ist jedoch anzunehmen, dass dann so viele Forscher sich an diese Problem machen würden, dass er früher oder später gefunden würde. Trotzdem würde die Welt nicht sofort aufhören zu funktionieren.


Edit:
Was ich auch noch nicht erwähnt habe:
Bloss weil es in polynominaler Zeit lösbar ist heisst das noch nicht unbedingt, dass es absehbarer Zeit lösbar ist. Denn wenn der Grad des Polynoms 100 ist wird es wohl auch nicht viel bringen

Wtf Bahnhof O_o xD

Reden wir hier allgemein von Problemen, von Problemen im Bereich Mathe, Problemen im Bereich Informatik oder von Problemen im Bereich Physik?

Wa für Probleme? Und was sind diese P und NP? xD"
Punkt und Nullpunkt?

Original von Ark
@Acrobat reader: Es geht darum, wie "schwierig" es ist, verschiedene Probleme zu lösen. In der Kryptographie baut man auf eher "schwierige" Probleme. Wäre nun P = NP, so wären viele Verschlüsselungsverfahren für den Allerwertesten, weil das auch hieße, dass die angeblich "schwierigen" Probleme gar nicht so schwierig sind. (Viel Spaß dann beim nächsten E-Mail-Abruf.)

Naja, du hast zwar Recht, dass in der Kryptographie viel auf "schwierige" Probleme gesetzt wird, aber wenn du dir z.B. RSA anschaust, dann basiert das nicht mal auf einem NP-Schwierigen Problem (bzw. man weiß es nicht genau - bisher konnte noch niemand zeigen, dass die Berechnung der Primzahlzerlegung NP-schwierig ist). Trotzdem wurde das bisher noch nicht wirklich effektiv gebrochen.

Andererseits basieren eigentlich alle symmetrischen Chiffren nichtmal ansatzweise auf NP-schwierigen Problemen. Die Schwierigkeit diese zu brechen liegt dann eher in der Komplexität der verwendeten Verfahren. Da wird dann halt so abgefahren substituiert und permutiert, dass es extrem schwierig ist, dass zu brechen - aber mit NP-schwierigen Problemen hat das nichts zu tun.

Wenn du dir das einzige wirklich beweisber unbrechbare Krypto-Verfahren ansiehst (One Time Pad) wirst du auch sehen, dass das prinzipiell sogar ganz einfach ist und die Sicherheit sich nicht aus einem solchen Betrachtungswinkel heraus ergibt.

Die Sache mit den NP-schwierigen Problemen ist dann eher für die Public Key Kryptographie interessant, denn da basiert die Sicherheit fast aller Verfahren wirklich auf solchen Problemen bzw. wie oben schon geschrieben sogar auf Problemen, die nicht unbedingt NP-schwierig sind. Wie gesagt, Primfaktorzerlegung ist ein großes Problem beim Brechen vieler Public Key Verfahren und dieses Problem besteht jetzt schon seit Jahren, ohne das es sinnvolle Fortschritte in diese Richtung gibt (wenn man mal von Quantencomputern absieht - aber Quantenkryptographie ist auch nochmal ein ganz anderes Thema, da ist die P & NP Sache noch viel egaler, weil die Sicherheit dann auf rein physikalischer Ebene gegeben wäre und man effektiv das One Time Pad Verfahren anwenden könnte). Von einer Apokalypse kann da nicht wirklich die Rede sein

Außerdem: P != NP wäre für andere Bereiche eine "Apokalypse". Man muss das immer aus verschiedenen Sichten sehen. Für die Algorithmik wäre P = NP eine feine Sache, für die Kryptographie eher nicht. Wie auch immer, egal wie die Antwort lautet, sie hätte weitreichende Folgen. Für manche Bereiche vermutlich sehr positive, für andere sehr negative. Da muss man dann halt jeweils kreativ werden und sich was Neues ausdenken

Ich bin auf jeden Fall mal gespannt, ob der Beweis hält oder nicht
Sehr interessante Sache! Ich hab ja immer gehofft, dass das noch jemand in meiner Lebzeit hinkriegt, hätte aber nicht damit gerechnet, dass es evtl. schon so bald der Fall sein könnte

ich wäre stark dafür das diese theorie stimmt.
anderer seits wäre so ziemlich alles was derzeit in der kryptographie passiert für den allerwertesten
Ganz davon abgesehen, es ist immer wieder interessant sich was zu dem thema durch zu lesen, wobei mathematische theorie immer probleme bereitet.
theoretisch ist jede theorie falsch, bis man ALLE möglichkeiten auf diese theorie angewendet hatt, die es gibt, und das zahlen spektrum sowohl anch oben als auch nach unten relativ offen sit, wird es niemal möglich sein alle möglichkeiten und anwendungsbeispiele auf diese theorie anzuwenden.
...ich erinnere mich wieder warum ich es gehasst habe mathemathishe beweise zu erbringen *gg*

Original von Saku
theoretisch ist jede theorie falsch, bis man ALLE möglichkeiten auf diese theorie angewendet hatt, die es gibt, und das zahlen spektrum sowohl anch oben als auch nach unten relativ offen sit, wird es niemal möglich sein alle möglichkeiten und anwendungsbeispiele auf diese theorie anzuwenden

Genau dafuer gibt's doch Beweise... um allgemeingueltig zu beweisen, dass etwas stimmt, auch ohne unendlich viele Moeglichkeiten ausprobieren zu muessen...

Original von Luna

Original von Saku
theoretisch ist jede theorie falsch, bis man ALLE möglichkeiten auf diese theorie angewendet hatt, die es gibt, und das zahlen spektrum sowohl anch oben als auch nach unten relativ offen sit, wird es niemal möglich sein alle möglichkeiten und anwendungsbeispiele auf diese theorie anzuwenden

Genau dafuer gibt's doch Beweise... um allgemeingueltig zu beweisen, dass etwas stimmt, auch ohne unendlich viele Moeglichkeiten ausprobieren zu muessen...

Ja, aber ich habe das prinzip noch nie verstanden was dahinter steht.
Prinzipiell heßt es ja das man allgemein gültig etwas beweisen kann, das es dann vorerst stimmt bis zum gegenbeweis.
Wenn du aber versuchst etwas mit variablen zu beweisen, musst du dich ja damit auch automatisch auf andere beweise beziehen die genau genommen auch nur annahmen sind, und somit wäre doch theoretisch die gewährleistung das die annahme korrekt ist falsch, oder?

z.b.:
Annahme:
x+1 = x+1
diese annahme wäre in jedem falle richtig, da sie ein gleichniss bildet, wenn man es jedoch wie
1+1 = 1+1, da 2 = 2
darstellt, so wird dies hinfällig, weil es, soweit ich das weiß, kein beweis sondern eine annahme ist, und nur für diesen fall funktioniert.

etwas schwieriger wäre es mit
(1/x)+(1/y) = (x*y)/(x+y), da 1/z = 1/z

Klar, kann das so funktionieren, aber niemand wüsste genau ob es geht ohne es selbst zu probieren - das war mein eigentlicher ansatz.

Original von Saku

Original von Luna

Original von Saku
theoretisch ist jede theorie falsch, bis man ALLE möglichkeiten auf diese theorie angewendet hatt, die es gibt, und das zahlen spektrum sowohl anch oben als auch nach unten relativ offen sit, wird es niemal möglich sein alle möglichkeiten und anwendungsbeispiele auf diese theorie anzuwenden

Genau dafuer gibt's doch Beweise... um allgemeingueltig zu beweisen, dass etwas stimmt, auch ohne unendlich viele Moeglichkeiten ausprobieren zu muessen...

Ja, aber ich habe das prinzip noch nie verstanden was dahinter steht.
Prinzipiell heßt es ja das man allgemein gültig etwas beweisen kann, das es dann vorerst stimmt bis zum gegenbeweis.
Wenn du aber versuchst etwas mit variablen zu beweisen, musst du dich ja damit auch automatisch auf andere beweise beziehen die genau genommen auch nur annahmen sind, und somit wäre doch theoretisch die gewährleistung das die annahme korrekt ist falsch, oder?

So etwas wie ein "Gegenbeweis" gibt es in der Mathematik nicht. Wenn in der Mathematik etwas bewiesen wird, dann gilt es für immer. Sie können sich auf alles stützen, was bereits bewiesen wurde. Und dann gibt es noch die grundsätzlichen Dinge, die sogenannten Axiome, die einfach als wahr angenommen werden müssen.

Ein Beweis ist es natürlich nur, wenn er korrekt ist und keine Fehler enthält.