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.

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 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. Given input, verify that it has the form and reject if it does not. If it has the correct form, simulate M. The simulation takes non-deterministic time, which is polynomial in the size of the input,. So, is in NP. By the assumption P = NP, there is also a deterministic machine DM that decides in polynomial time. We can then decide L in deterministic exponential time as follows. Given input, simulate. This takes only exponential time in the size of the input,.
The 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.