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
Since L is in NEXP, there is a non-deterministic Turing machine M that decides L in time
for some constant c. Let where '1' is a symbol not occurring in L. First we show that
is in NP, then we will use the deterministic polynomial time machine given by P = NP to show that L is in EXP.
can be decided in non-deterministic polynomial time as follows.
If it has the correct form, simulate M(x).
The simulation takes non-deterministic
time, which is polynomial in the size of the input,
By the assumption P = NP, there is also a deterministic machine DM that decides
We can then decide L in deterministic exponential time as follows.
This takes only exponential time in the size of the input,
is called the "padding" of the language L. This type of argument is also sometimes used for space complexity classes, alternating classes, and bounded alternating classes.