Padding argument

In computational complexity theory, the padding argument is a tool to conditionally prove that if some complexity classes are equal, then some other bigger classes are also equal.

The proof that P = NP implies EXP = NEXP uses "padding". ${\displaystyle \mathrm {EXP} \subseteq \mathrm {NEXP} }$ by definition, so it suffices to show ${\displaystyle \mathrm {NEXP} \subseteq \mathrm {EXP} }$.

Let L be a language in NEXP. Since L is in NEXP, there is a non-deterministic Turing machine M that decides L in time ${\displaystyle 2^{n^{c}}}$ for some constant c. Let

...
Wikipedia