Lexikon der Mathematik: pseudopolynomielle Rechenzeiten
Rechenzeiten, die polynomiell bezogen auf die Eingabelänge und die Größe der in der Eingabe vorkommenden Zahlen sind.
Ein Algorithmus mit pseudopolynomieller Rechenzeit hat für Eingaben, die nur polynomiell große Zahlen beinhalten, polynomielle Rechenzeit. Derartige Algorithmen gibt es für das Rucksackproblem und die Primzahlerkennung. Für ein streng NP-vollständiges Problem kann es einen Algorithmus mit pseudopolynomieller Rechenzeit nur geben, wenn NP=P (NP-Vollständigkeit) ist.
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.