Padding argument

EXP=NEXP

Theorem. If P = NP then EXP = NEXP.

Proof. ${\displaystyle {\mathsf {EXP}}\subseteq {\mathsf {NEXP}}}$ by definition, so it suffices to show ${\displaystyle {\mathsf {NEXP}}\subseteq {\mathsf {EXP}}}$.

Let L be a language in NEXP, so there is a non-deterministic Turing machine M that verifies ${\displaystyle x\in L}$ in nondeterministic time ${\displaystyle 2^{|x|^{c}}}$, for some constant natural number c. Now define the padded language

${\displaystyle L'=\{x1^{2^{|x|^{c}}}\mid x\in L\},}$

where '1' is a symbol not occurring in L.

${\displaystyle L'}$ is in NP: Given input ${\displaystyle x'}$, first verify that it has the form ${\displaystyle x'=x1^{2^{|x|^{c}}}}$ and reject if it does not. If it has the correct form, verify ${\displaystyle x\in L}$ using M, which takes non-deterministic time ${\displaystyle 2^{|x|^{c}}={\mathsf {poly}}(|x'|)}$.

By the assumption P = NP, ${\displaystyle L'}$ is in P, so there is a deterministic machine DM that decides ${\displaystyle L'}$ in polynomial time.

We can then decide L in deterministic exponential time. Given input ${\displaystyle x}$, write down ${\displaystyle x'=x1^{2^{|x|^{c}}}}$, and use DM to decide if ${\displaystyle x'\in L'}$. This takes time ${\displaystyle {\mathsf {poly}}(|x|+2^{|x|^{c}})={\mathsf {EXP}}(|x|)}$.

Ladner's theorem

Another theorem proven by the padding argument is

Ladner's theorem. If ${\displaystyle {\mathsf {P}}\neq {\mathsf {NP}}}$ then there exists a computational problem that is NP-intermediate: in ${\displaystyle {\mathsf {NP}}\setminus {\mathsf {P}}}$ but not NP-complete.

Proof. Assume that ${\displaystyle {\mathsf {P}}\neq {\mathsf {NP}}}$. Let SAT be the satisfiable formula language. It is NP-complete. Now, given any function ${\displaystyle H:\mathbb {N} \to \mathbb {N} }$ such that ${\displaystyle H(n)}$ is computable in ${\displaystyle {\mathsf {poly}}(n)}$ time, we can define the padded language$${\displaystyle {\mathsf {SAT}}^{*}:=\{\phi 1^{|\phi |^{H(|\phi |)}}:\phi \in {\mathsf {SAT}}\}}$$Claim 1: SAT* is NP. This is demonstrated by this algorithm

• Given a formula ${\displaystyle \phi }$, if it does not conform to the format of SAT*, return False.
• Else, remove its padding to obtain a shorter formula ${\displaystyle \phi '}$, and test whether the padding has length ${\displaystyle H(|\phi '|)}$. If not, return False.
• Else, check if ${\displaystyle \phi '\in {\mathsf {SAT}}}$ in nondeterministic time ${\displaystyle {\mathsf {poly}}(|\phi '|)\leq {\mathsf {poly}}(|\phi |)}$.

Claim 2: If ${\displaystyle H}$ is bounded, then SAT* is NP-complete. Since ${\displaystyle H}$ is bounded, padding takes in polynomial time, reducing SAT to SAT*.

Claim 3: If ${\displaystyle H\to \infty }$, then SAT* is not NP-complete.

Assume otherwise, then there is an algorithm ${\displaystyle T}$, which reduces the SAT problem to SAT* in time ${\displaystyle n^{c}}$. Then, we can decide SAT in polynomial time as follows:

• Given some formula ${\displaystyle \phi }$, if ${\displaystyle T(\phi )}$ does not conform to the format of SAT*, return False.
• Else, by runtime upper bound, ${\displaystyle |\phi _{1}|^{H(|\phi _{1}|)}+|\phi _{1}|=|\phi _{1}1^{|\phi _{1}|^{H(|\phi _{1}|)}}|=|T(\phi )|\leq |\phi |^{c}}$.
• We repeat this process, each time obtaining a shorter formula ${\displaystyle \phi _{1},\phi _{2},\dots }$ until we either
  • hit a formula that does not conform to the format of SAT*, and we return False
  • or obtain a formula ${\displaystyle \phi _{k}}$ with length ${\displaystyle |\phi _{k}|\leq C}$ for some constant ${\displaystyle C}$, in which case we simply brute force enumerate all ${\displaystyle O(2^{C})}$ possible truth value assignments for ${\displaystyle \phi _{k}}$. If ${\displaystyle \phi _{k}}$ is satisfiable, then return True, else return False.

Provided that ${\displaystyle C}$ is chosen large enough so that ${\displaystyle H(m)>2c}$ for all ${\displaystyle m>C}$, we can make it so that every iteration reduces the length: $${\displaystyle |\phi _{1}|^{2}\leq |\phi |,|\phi _{2}|^{2}\leq |\phi _{1}|,\dots ,|\phi _{k}|^{2^{k}}\leq |\phi |}$$Thus, this requires ${\displaystyle k=O(\ln \ln |\phi |)}$ iterations, and thus the whole algorithm runs in time ${\displaystyle {\mathsf {poly}}(|\phi |)}$. The idea is similar to kernelization.

Step 4: Construct an ${\displaystyle H}$, such that ${\displaystyle H}$ is polytime computable, ${\displaystyle H\to \infty }$, and SAT* is not P.

Define ${\displaystyle H}$ as follows: ${\displaystyle H(0)=0,H(1)=1}$, and for larger ${\displaystyle n}$, ${\displaystyle H(n)}$ is the smallest positive integer ${\displaystyle i}$, such that

• ${\displaystyle i\leq f(n)}$.
• For any ${\displaystyle \phi }$ of length ${\displaystyle |\phi |<g(n)}$, the Turing machine ${\displaystyle M_{i}}$ correctly decides ${\displaystyle \phi \in {\mathsf {SAT}}^{*}}$ with runtime ${\displaystyle \leq i|\phi |^{i}}$.

• If no such Turing machine exists, then simply set ${\displaystyle H(n)=f(n)}$.

where ${\displaystyle f(n)=g(n)=\lceil \ln \ln n\rceil }$ are two functions designed to make ${\displaystyle H(n)}$ computable in time ${\displaystyle {\mathsf {poly}}(n)}$.

Claim: ${\displaystyle H(n)}$ is well-defined and computable in ${\displaystyle {\mathsf {poly}}(n)}$.

This is shown by induction on ${\displaystyle n}$. The base cases are simply memorized. For the induction step, test all ${\displaystyle f(n)}$ Turing machines on all ${\displaystyle 2^{g(n)}}$ possible formulas ${\displaystyle \phi }$ of length ${\displaystyle |\phi |\leq g(n)}$, for ${\displaystyle i|\phi |^{i}\leq f(n)g(n)^{f(n)}}$ steps. We also need to test whether ${\displaystyle \phi \in {\mathsf {SAT}}^{*}}$, which takes up to ${\displaystyle 2^{g(n)}}$ time by checking all rows of its truth table. The total time taken is bounded above by $${\displaystyle f(n)2^{g(n)}f(n)g(n)^{f(n)}+2^{g(n)}2^{g(n)}\leq {\mathsf {poly}}(n)}$$Now, if SAT* is in P, then let ${\displaystyle M_{m}}$ be a machine that decides SAT* in time ${\displaystyle Cn^{C'}}$. For sufficiently large ${\displaystyle n}$ such that ${\displaystyle f(n)>\max(C,C',m)}$, the construction allows ${\displaystyle M_{m}}$ to be considered in the construction of ${\displaystyle H(n)}$. This shows that, for all large enough ${\displaystyle n}$, we have ${\displaystyle H(n)=m}$, and so by claim 2, SAT* is NP-complete, but then we have an NP-complete problem that is in P, contradicting the assumption that ${\displaystyle {\mathsf {P}}\neq {\mathsf {NP}}}$.

Thus, SAT* is not in P. This implies that ${\displaystyle H(n)}$ would be forced to grow towards infinity. By Claim 3, SAT* is not NP-complete.