Wenn dies dein erster Besuch hier ist, lese bitte zuerst die Hilfe - Häufig gestellte Fragen durch. Du musst dich registrieren, bevor du Beiträge verfassen kannst. Du kannst auch jetzt schon Beiträge lesen. Suche dir einfach das Forum aus, das dich am meisten interessiert.
p sind alle probleme, die "schnell" lösbar sind, np sind alle Probleme, die mit konventioneller Rechentechnik eben nicht "schnell" lösbar sind bzw. die sich mit nicht-konventioneller Technik "schnell" lösen lassen.
Kandidaten für diese nichtkonventionelle Technik wären die Quantencomputer, allerdings hat sich da schon gezeigt, dass die das Problem nicht direkt komplett umgehen können.
Wenn tatsächlich p != np, dann gibt es für eine ganze Menge von wichtigen Problemen keine effizienten Algorithmen.
z.b. Wegfindung. allerdings gibts in vielen Fällen Algorithmen, die Näherungslösungen produzieren, die so nah am Optimum sind, dass es egal is und das dann wieder "schnell" schaffen.
Kommentar