Padding argument

Template:Short description 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. This type of argument is also sometimes used for space complexity classes, alternating classes, and bounded alternating classes.

Example

EXP=NEXP

Theorem. If P = NP then EXP = NEXP.

Proof. $𝖤𝖷𝖯\subseteq 𝖭𝖤𝖷𝖯$ by definition, so it suffices to show $𝖭𝖤𝖷𝖯\subseteq 𝖤𝖷𝖯$.

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

$L^{\prime }=\{x{1}^{2^{|x{|}^c}}\mid x\in L\},$

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

$L^{\prime }$ is in NP: Given input $x^{\prime }$, first verify that it has the form $x^{\prime }=x{1}^{2^{|x{|}^c}}$ and reject if it does not. If it has the correct form, verify $x\in L$ using M, which takes non-deterministic time $2^{|x{|}^c}=𝗉𝗈𝗅𝗒(|x^{\prime }|)$.

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

We can then decide L in deterministic exponential time. Given input $x$, write down $x^{\prime }=x{1}^{2^{|x{|}^c}}$, and use DM to decide if $x^{\prime }\in L^{\prime }$. This takes time $𝗉𝗈𝗅𝗒(|x|+2^{|x{|}^c})=𝖤𝖷𝖯(|x|)$.

Ladner's theorem

Another theorem proven by the padding argument is

Ladner's theorem. If $𝖯\ne 𝖭𝖯$ then there exists a computational problem that is NP-intermediate: in $𝖭𝖯\setminus 𝖯$ but not NP-complete.

Proof. Assume that $𝖯\ne 𝖭𝖯$. Let SAT be the satisfiable formula language. It is NP-complete. Now, given any function $H:\mathbb{N}\to \mathbb{N}$ such that $H(n)$ is computable in $𝗉𝗈𝗅𝗒(n)$ time, we can define the padded language$${𝖲𝖠𝖳}^{\ast }:=\{\varphi 1^{|\varphi {|}^{H(|\varphi |)}}:\varphi \in 𝖲𝖠𝖳\}$$Claim 1: SAT* is NP. This is demonstrated by this algorithm

• Given a formula $\varphi$, if it does not conform to the format of SAT*, return False.
• Else, remove its padding to obtain a shorter formula ${\varphi }^{\prime }$, and test whether the padding has length $H(|{\varphi }^{\prime }|)$. If not, return False.
• Else, check if ${\varphi }^{\prime }\in 𝖲𝖠𝖳$ in nondeterministic time $𝗉𝗈𝗅𝗒(|{\varphi }^{\prime }|)\le 𝗉𝗈𝗅𝗒(|\varphi |)$.

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

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

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

• Given some formula $\varphi$, if $T(\varphi )$ does not conform to the format of SAT*, return False.
• Else, by runtime upper bound, $|{\varphi }_1{|}^{H(|{\varphi }_1|)}+|{\varphi }_1|=|{\varphi }_1{1}^{|{\varphi }_1{|}^{H(|{\varphi }_1|)}}|=|T(\varphi )|\le |\varphi {|}^c$.
• We repeat this process, each time obtaining a shorter formula ${\varphi }_1,{\varphi }_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 ${\varphi }_k$ with length $|{\varphi }_k|\le C$ for some constant $C$, in which case we simply brute force enumerate all $O(2^C)$ possible truth value assignments for ${\varphi }_k$. If ${\varphi }_k$ is satisfiable, then return True, else return False.

Provided that $C$ is chosen large enough so that $H(m)>2c$ for all $m>C$, we can make it so that every iteration reduces the length: $$|{\varphi }_1{|}^2\le |\varphi |,|{\varphi }_2{|}^2\le |{\varphi }_1|,\dots ,|{\varphi }_k{|}^{2^k}\le |\varphi |$$Thus, this requires $k=O(\ln \ln |\varphi |)$ iterations, and thus the whole algorithm runs in time $𝗉𝗈𝗅𝗒(|\varphi |)$. The idea is similar to kernelization.

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

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

• $i\le f(n)$.
• For any $\varphi$ of length $|\varphi |<g(n)$, the Turing machine $M_i$ correctly decides $\varphi \in {𝖲𝖠𝖳}^{\ast }$ with runtime $\le i|\varphi {|}^i$.

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

where $f(n)=g(n)=\lceil \ln \ln n\rceil$ are two functions designed to make $H(n)$ computable in time $𝗉𝗈𝗅𝗒(n)$.

Claim: $H(n)$ is well-defined and computable in $𝗉𝗈𝗅𝗒(n)$.

This is shown by induction on $n$. The base cases are simply memorized. For the induction step, test all $f(n)$ Turing machines on all $2^{g(n)}$ possible formulas $\varphi$ of length $|\varphi |\le g(n)$, for $i|\varphi {|}^i\le f(n)g(n{)}^{f(n)}$ steps. We also need to test whether $\varphi \in {𝖲𝖠𝖳}^{\ast }$, which takes up to $2^{g(n)}$ time by checking all rows of its truth table. The total time taken is bounded above by $$f(n)2^{g(n)}f(n)g(n{)}^{f(n)}+2^{g(n)}{2}^{g(n)}\le 𝗉𝗈𝗅𝗒(n)$$Now, if SAT* is in P, then let $M_m$ be a machine that decides SAT* in time $C{n}^{C^{\prime }}$. For sufficiently large $n$ such that $f(n)>max(C,C^{\prime },m)$, the construction allows $M_m$ to be considered in the construction of $H(n)$. This shows that, for all large enough $n$, we have $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 $𝖯\ne 𝖭𝖯$.

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

See also

• Paddable language
• NP-intermediate

References

• Arora, Sanjeev; Barak, Boaz (2009), Computational Complexity: A Modern Approach, Cambridge, p. 57, ISBN 978-0-521-42426-4