In der Komplexitätstheorie wird ein Algorithmus pseudopolynomiell genannt, wenn seine Laufzeit ein Polynom im numerischen Wert der Eingabe ist. Der Unterschied wird deutlich, wenn man dies mit einem echt polynomiellen Algorithmus vergleicht wie z. B. dem Algorithmus zur Addition von Zahlen: Das Addieren zweier 9-stelliger Zahlen benötigt etwa 9 ...