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.