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".

[math]\displaystyle{ \mathrm{EXP} \subseteq \mathrm{NEXP} }[/math] by definition, so it suffices to show [math]\displaystyle{ \mathrm{NEXP} \subseteq \mathrm{EXP} }[/math].

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 [math]\displaystyle{ 2^{n^c} }[/math] for some constant c. Let

[math]\displaystyle{ L'=\{x1^{2^{|x|^c}} \mid x \in L\}, }[/math]

where '1' is a symbol not occurring in L. First we show that [math]\displaystyle{ L' }[/math] is in NP, then we will use the deterministic polynomial time machine given by P = NP to show that L is in EXP.

[math]\displaystyle{ L' }[/math] can be decided in non-deterministic polynomial time as follows. Given input [math]\displaystyle{ x' }[/math], verify that it has the form [math]\displaystyle{ x' = x1^{2^{|x|^c}} }[/math] and reject if it does not. If it has the correct form, simulate M(x). The simulation takes non-deterministic [math]\displaystyle{ 2^{|x|^c} }[/math] time, which is polynomial in the size of the input, [math]\displaystyle{ x' }[/math]. So, [math]\displaystyle{ L' }[/math] is in NP. By the assumption P = NP, there is also a deterministic machine DM that decides [math]\displaystyle{ L' }[/math] in polynomial time. We can then decide L in deterministic exponential time as follows. Given input [math]\displaystyle{ x }[/math], simulate [math]\displaystyle{ DM(x1^{2^{|x|^c}}) }[/math]. This takes only exponential time in the size of the input, [math]\displaystyle{ x }[/math].

The [math]\displaystyle{ 1^d }[/math] 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.

References

• Computational Complexity: A Modern Approach, Cambridge University Press, 2009, p. 57, ISBN 978-0-521-42426-4, http://www.cs.princeton.edu/theory/complexity/