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.

Example

The proof that P = NP implies EXP = NEXP uses "padding". by definition, so it suffices to show. 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 2^{n^c} for some constant c. Let where '1' is a symbol not occurring in L. First we show that L' is in NP, then we will use the deterministic polynomial time machine given by P = NP to show that L is in EXP. L' can be decided in non-deterministic polynomial time as follows. Given input x', verify that it has the form and reject if it does not. If it has the correct form, simulate M(x). The simulation takes non-deterministic 2^{|x|^c} time, which is polynomial in the size of the input, x'. So, L' is in NP. By the assumption P = NP, there is also a deterministic machine DM that decides L' in polynomial time. We can then decide L in deterministic exponential time as follows. Given input x, simulate. This takes only exponential time in the size of the input, x. The 1^d 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.