Wäre damit das P-NP Problem gelöst?
Also für alle, die nicht wissen, was es ist, es ist eines der Millenium Probleme, welches noch nicht gelöst wurde.
Kurze Zusammenfassung der Frage des P-NP Problems:
Bedeutet die Fähigkeit, korrekte Antworten schnell zu erkennen (NP) auch, dass es eine schnelle Möglichkeit gibt, diese Antworten zu finden (P)?
Beispiel:
Man hate einen Zauberwürfel mit auf jeder Seite hunderten Feldern, sobald er "gelöst" wird, kann man schnell erkennen, ob er richtig oder falsch gelöst wurde, allerdings würde man (nach dem heutigen Wissensstand) nahezu ewig brauchen, um ihn überhaupt lösen zu können, die Frage ist da halt: gibt es eine Möglichkeit, ihn schnell lösen zu können, da man ja auch schnell sehen kann, ob er richtig oder falsch gelöst ist.
Meine "Lösung" (als Gedankenexperiment; noch nicht rechnerisch nachgewiesen):
Man will ein Passwort hacken, weshalb man einen Algorithmus schreibt, welcher die Passwörter einzeln durchgeht (Problem in NP). Da wird ja schnell erkannt, ob ein Passwort richtig oder falsch ist (dadurch, dass man dann eingeloggt ist oder eben nicht), allerdings gibt es keine Möglichkeit, es anders herauszufinden, da es eben einfach keinen anderen Lösungsweg gibt. Also gibt es auch keinen schnelleren Lösungsweg, weshalb nur an diesem Beispiel theoretisch nachgewiesen wäre, dass P≠NP ist oder?
Ich würde mich über sachliche Antworten sehr freuen, mir ist bewusst, dass meine Antwort vermutlich viel zu einfach ist, damit sie als Lösung gesehen werden könnte und das andere Leute diese Idee vermutlich auch schon hatten. Mich würden nur eure Gedanken dazu interessieren!
2 Antworten
Ich verstehe nicht ganz, wie du auf P != NP kommst.
Deine Idee verwendet "Passwort erraten" als Problem und du suchst nach einem Algorithmus, der das richtige Passwort in polynomieller Zeit zur Eingabelänge findet.
Die Anzahl der Möglichkeiten, die man bei einer Passwortlänge n und m möglichen Buchstaben/Zahlen/Sonderzeichen testen muss, beträgt m^n und ist daher in exponentieller Zeit zur Eingabelänge. Daraus kannst du nur folgern, dass "Passwort erraten" nicht in NP liegt. Generell ist das auch kein geschicktes Beispiel, weil dein Algorithmus naiv alle Möglichkeiten ausprobiert und nicht besser sein kann, weil jedes Passwort prinzipiell gleich wahrscheinlich ist und kein Passwort durch gesammeltes "Vorwissen" von anderen (falschen) Passwörtern ausgeschlossen werden kann.
Hoffe, das hat geholfen :)
Ja, auf jeden Fall! War auch nur ein völlig übermüdeter und dummer Gedanke von mir xD
Du hast keine einzige Voraussetzung aufgestellt und keine einzige Schlußfolgerung daraus gezogen. Damit hast du nichts gezeigt.