Padding argument

Short description: Proof technique in computational complexity theory

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. $\mathsf{E}\mathsf{X}\mathsf{P}\subseteq \mathsf{N}\mathsf{E}\mathsf{X}\mathsf{P}$ by definition, so it suffices to show $\mathsf{N}\mathsf{E}\mathsf{X}\mathsf{P}\subseteq \mathsf{E}\mathsf{X}\mathsf{P}$.

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}=\mathsf{p}\mathsf{o}\mathsf{l}\mathsf{y}(|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 $\mathsf{p}\mathsf{o}\mathsf{l}\mathsf{y}(|x|+2^{|x{|}^c})=\mathsf{E}\mathsf{X}\mathsf{P}(|x|)$.

Ladner's theorem

Another theorem proven by the padding argument is

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

Proof. Assume that $\mathsf{P}\ne \mathsf{N}\mathsf{P}$. Let SAT be the satisfiable formula language. It is NP-complete. Now, given any function $H:\mathbb{\mathbb{N}}\to \mathbb{\mathbb{N}}$ such that $H(n)$ is computable in $\mathsf{p}\mathsf{o}\mathsf{l}\mathsf{y}(n)$ time, we can define the padded language$${\mathsf{S}\mathsf{A}\mathsf{T}}^{*}:=\{\varphi 1^{|\varphi {|}^{H(|\varphi |)}}:\varphi \in \mathsf{S}\mathsf{A}\mathsf{T}\}$$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 \mathsf{S}\mathsf{A}\mathsf{T}$ in nondeterministic time $\mathsf{p}\mathsf{o}\mathsf{l}\mathsf{y}(|{\varphi }^{\prime }|)\le \mathsf{p}\mathsf{o}\mathsf{l}\mathsf{y}(|\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 $\mathsf{p}\mathsf{o}\mathsf{l}\mathsf{y}(|\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 {\mathsf{S}\mathsf{A}\mathsf{T}}^{*}$ 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 $\mathsf{p}\mathsf{o}\mathsf{l}\mathsf{y}(n)$.

Claim: $H(n)$ is well-defined and computable in $\mathsf{p}\mathsf{o}\mathsf{l}\mathsf{y}(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 {\mathsf{S}\mathsf{A}\mathsf{T}}^{*}$, 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 \mathsf{p}\mathsf{o}\mathsf{l}\mathsf{y}(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 $\mathsf{P}\ne \mathsf{N}\mathsf{P}$.

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

• Computational Complexity: A Modern Approach, Cambridge, 2009, p. 57, ISBN 978-0-521-42426-4, http://www.cs.princeton.edu/theory/complexity/