Padding argument (original) (raw)
From Wikipedia, the free encyclopedia
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".
E X P ⊆ N E X P {\displaystyle \mathrm {EXP} \subseteq \mathrm {NEXP} } by definition, so it suffices to show N E X P ⊆ E X P {\displaystyle \mathrm {NEXP} \subseteq \mathrm {EXP} }
.
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 {\displaystyle 2^{n^{c}}} for some constant c. Let
L ′ = { x 1 2 | x | c ∣ x ∈ L } , {\displaystyle L'=\{x1^{2^{|x|^{c}}}\mid x\in L\},}
where '1' is a symbol not occurring in L. First we show that L ′ {\displaystyle 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 ′ {\displaystyle L'} can be decided in non-deterministic polynomial time as follows. Given input x ′ {\displaystyle x'}
, verify that it has the form x ′ = x 1 2 | x | c {\displaystyle x'=x1^{2^{|x|^{c}}}}
and reject if it does not. If it has the correct form, simulate M(x). The simulation takes non-deterministic 2 | x | c {\displaystyle 2^{|x|^{c}}}
time, which is polynomial in the size of the input, x ′ {\displaystyle x'}
. So, L ′ {\displaystyle L'}
is in NP. By the assumption P = NP, there is also a deterministic machine DM that decides L ′ {\displaystyle L'}
in polynomial time. We can then decide L in deterministic exponential time as follows. Given input x {\displaystyle x}
, simulate D M ( x 1 2 | x | c ) {\displaystyle DM(x1^{2^{|x|^{c}}})}
. This takes only exponential time in the size of the input, x {\displaystyle x}
.
The 1 d {\displaystyle 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.