padding argument

The proof that P = NP implies EXP = NEXP uses "padding".

$\backslash mathrm\{EXP\}\; \backslash subseteq\; \backslash mathrm\{NEXP\}$ by definition, so it suffices to show $\backslash mathrm\{NEXP\}\; \backslash subseteq\; \backslash 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\}$ for some constant c. Let

: $L\text{'}=\backslash \{x1^\{2^\{|x|^c\}\}\; \backslash mid\; x\; \backslash in\; L\backslash \},$

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

$L\text{'}$ can be decided in non-deterministic polynomial time as follows. Given input $x\text{'}$, verify that it has the form $x\text{'}\; =\; 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\}$ time, which is polynomial in the size of the input, $x\text{'}$. So, $L\text{'}$ is in NP. By the assumption P = NP, there is also a deterministic machine DM that decides $L\text{'}$ in polynomial time. We can then decide L in deterministic exponential time as follows. Given input $x$, simulate $DM(x1^\{2^\{|x|^c\}\})$. This takes only exponential time in the size of the input, $x$.

The $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.

• Paddable language

• {{Citation

| last1=Arora | first1=Sanjeev | authorlink1=Sanjeev Arora

| last2=Barak | first2=Boaz|author2link = Boaz Barak

| title=Computational Complexity: A Modern Approach

| url = http://www.cs.princeton.edu/theory/complexity/

| publisher=Cambridge

| year=2009

| isbn=978-0-521-42426-4

| page = 57

}}

{{DEFAULTSORT:Computational Complexity Theory}}

*