Padding technique

The padding technique is a method of complexity theory to prove that the equality of certain complexity classes leads to greater equality.

example

The proof that follows from also uses padding. Since, by definition, it is enough to show. (Because of the contraposition , this also shows that it also follows.) ${\displaystyle \mathrm {P} =\mathrm {NP} }$ ${\displaystyle \mathrm {EXP} =\mathrm {NEXP} }$ ${\displaystyle \mathrm {EXP} \subseteq \mathrm {NEXP} }$ ${\displaystyle \mathrm {EXP} \supseteq \mathrm {NEXP} }$ ${\displaystyle \mathrm {EXP} \neq \mathrm {NEXP} }$ ${\displaystyle \mathrm {P} \neq \mathrm {NP} }$

Let and be a suitable nondeterministic Turing machine with running time for a fixed dependent on . Now construct a new language by adding a certain number to 1's to each word: ${\displaystyle L\in \mathrm {NEXP} }$ ${\displaystyle N}$ ${\displaystyle {\mathcal {O}}(2^{n^{c}})}$ ${\displaystyle c}$ ${\displaystyle L}$ ${\displaystyle L'}$

${\displaystyle L':=\left\{x\ 1^{2^{|x|^{c}}}\mid x\in L\right\}}$

whereby . This padding artificially inflates the length of the words without significantly increasing the difficulty of the decision problem. With this construction is as set out below. It is then derived from the assumption that . ${\displaystyle 1\notin L}$ ${\displaystyle L'\in \mathrm {NP} }$ ${\displaystyle \mathrm {P} =\mathrm {NP} }$ ${\displaystyle L\in \mathrm {EXP} }$

${\displaystyle L'}$can for input as follows in non-deterministic polynomial time decision , check if: be of the form , and discard, if this is not the case. Otherwise simulate the nondeterministic Turing machine with input . The simulation takes the time nondeterministically , which is polynomial in the size of . Hence is . ${\displaystyle x'}$ ${\displaystyle x'}$ ${\displaystyle x'=x\ 1^{2^{{|x|}^{c}}}}$ ${\displaystyle N}$ ${\displaystyle x}$ ${\displaystyle {\mathcal {O}}(2^{{|x|}^{c}})}$ ${\displaystyle x'}$ ${\displaystyle L'\in \mathrm {NP} }$

With the assumption there is a deterministic machine that decides in polynomial time. The language can then be decided in exponential time by simulating the machine on the input for an input . This only takes an exponential amount of time, depending on the input size. ${\displaystyle \mathrm {P} =\mathrm {NP} }$ ${\displaystyle D}$ ${\displaystyle L'}$ ${\displaystyle L}$ ${\displaystyle x}$ ${\displaystyle D}$ ${\displaystyle x\ 1^{2^{{|x|}^{c}}}}$

This argument is sometimes used for space complexity , alternating classes, and constrained alternating classes .

See also

• P-NP problem
• EXP and NEXP

literature

• Sanjeev Arora , Boaz Barek (2009): Computational Complexity: A Modern Approach. Cambridge University Press, Cambridge / New York 2009, ISBN 978-0-521-42426-4 , p. 57.