künstliche Verlängerung der Eingaben eines Problems P.

Gültige Eingaben für das durch Padding bzgl. der Funktion g (an die schwache Voraussetzungen gestellt werden) erzeugte neue Problem P_g sind Eingaben w der Länge n für das Problem P gefolgt von g(n) Buchstaben #. Dabei ist # ein im bisherigen Eingabealphabet nicht enthaltener Buchstabe. Da die Rechenzeit in Abhängigkeit von der Eingabelänge gemessen wird, hat ein aus einem Algorithmus A für P abgeleiteter Algorithmus A_g für P_g eine geringere Komplexität (Komplexität von Algorithmen) als P.

Mit der Padding-Technik läßt sich der Translationssatz beweisen.