Warum ist P-NP -Problem so wichtig?
2 Antworten
Eine ganze Reihe von Verschlüsselungsverfahren beruht auf mathematischen Problemen, die in NP liegen (z. B. die Faktorisierung von sehr großen Zahlen), von denen wir aber keinen Algorithmus kennen, der das Problem in polynomialer Zeit löst.
Wenn wir wissen, dass NP gleich P ist, dann wissen wir, dass es einen solchen Algorithmus geben muss, und das die Verfahren darum auch theoretisch zu knacken sind. Wenn wir wissen, dass NP nicht gleich P ist, dann wissen wir, dass es einen solchen Algorithmus nicht geben kann.
NP sagt ja auch erstmal gar nix darüber aus, wie schnell der Algorithmus zum Finden der Lösung ist. Darum geht es ja nicht (nein, NP heißt NICHT nicht polynomial). Und natürlich gibt es NP-Probleme, für die es schnelle Lösungsalgorithmen gibt. DAS ist nicht die Frage, die hinter dem P-NP-Problem steht. Es geht ja darum, ob es für alle NP-Probleme P-Lösungsalgorithmen gibt.
die Verfahren darum [...] zu knacken sind
hörte sich anders an... aber ich weiß schon, dass du das Richtige meinst... daher das „duck“... ich kann nämlich keine Mathematiker zurückschlagen... auch keine Frauen... und auch sonst lieber niemanden...
Ok, ich verstehe, was du meinst. Auch wenn man wüsste, dass NP nicht gleich P ist (was man zur Zeit ja eher anzunehmen scheint, wenn solch eine vage Formulierung mir als Mathematikerin gestattet sein mag), kann man sich nicht sicher sein, dass man für bestimmte Instanzen nicht "schnelle" Lösungen finden kann. Und da sowieso alle "einfacheren" Probleme (also alles, was sowieso schon in P oder in Klassen "darunter" liegt) auch in NP liegen (sofern man sie als Entscheidungsproblem formuliert), muss man dann noch mal mit der Formulierung aufpassen.
ich meinte, wenn es einen Algorithmus gibt, der eine n-stellige Zahl in 2^((10^-100)*n) Rechenschritten faktorisiert, dann wäre der zwar nicht in P, aber schneller solange n nich ausgerechnet in die Nähe von 10^102 kommt... so... kicher
Um zu untersuchen ob Probleme maschinell lösbar sind. Es wäre sinnlos was zu entwickeln, wenn es schon von vornherein klar ist, dass ein Problem nicht maschinell zu lösen ist.
ein Algo in NP kann bei bestimmten Instanzen schneller sein als einer aus P.... *duck*