Padding argument explained

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

EXP\subseteqNEXP

by definition, so it suffices to show

NEXP\subseteqEXP

.

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

nc
2
for some constant c. Let
|x|c
2
L'=\{x1

\midx\inL\},

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

x'=

|x|c
2
x1
and reject if it does not. If it has the correct form, simulate M(x). The simulation takes non-deterministic
|x|c
2
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
|x|c
2
DM(x1

)

. This takes only exponential time in the size of the input,

x

.

The

1d

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.

See also