Lexikon der Mathematik: P
die Komplexitätsklasse aller durch polynomiale Algorithmen (polynomialer Algorithmus) lösbaren Probleme.
Ein Problem ist bzgl. der worst case Rechenzeit nur dann effizient lösbar, wenn es in P enthalten ist. Im Rahmen der Theorie der NP-Vollständigkeit wird P auf Entscheidungsprobleme (Entscheidungsproblem) eingeschränkt, ohne dies in der Notation kenntlich zu machen.
Copyright Springer Verlag GmbH Deutschland 2017
Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.