Das Problem P vs NP ist eines der zentralen ungelösten Probleme der theoretischen Informatik. Es beschäftigt sich mit der Frage, ob jede Aufgabe, die in polynomialer Zeit verifiziert werden kann (NP), auch in polynomialer Zeit gelöst werden kann (P). Formal ausgedrückt, fragt man, ob oder gilt. Wenn wahr ist, würde dies bedeuten, dass es für jede Aufgabe, deren Lösung schnell überprüft werden kann, auch einen schnellen Algorithmus zur Lösung dieser Aufgabe gibt. Viele Probleme, wie das Handlungsreisendenproblem oder das Clique-Problem, fallen in die NP-Kategorie, und ihre effiziente Lösung könnte bedeutende Auswirkungen auf Bereiche wie Kryptographie, Optimierung und künstliche Intelligenz haben. Bislang ist jedoch kein Algorithmus bekannt, der zeigt, dass gilt, und die Mehrheit der Informatiker tendiert zur Annahme, dass ist.
Starte dein personalisiertes Lernelebnis mit acemate. Melde dich kostenlos an und finde Zusammenfassungen und Altklausuren für deine Universität.