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{EXP} \subseteq \mathsf{NEXP} by definition, so it suffices to show \mathsf{NEXP} \subseteq \mathsf{EXP}.

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'=\{x1^{2^{|x|^c}} \mid x \in L\},

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

L' is in NP: Given input x', first verify that it has the form x' = x1^{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{poly}(|x'|).

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

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

Ladner's theorem

Another theorem proven by the padding argument is

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

Proof. Assume that \mathsf{P} \neq \mathsf{NP}. Let SAT be the satisfiable formula language. It is NP-complete. Now, given any function H: \N \to \N such that H(n) is computable in \mathsf{poly}(n) time, we can define the padded language

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

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 \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 \phi, if T(\phi) does not conform to the format of SAT*, return False.
  • Else, by runtime upper bound, |\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 \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 \phi_k with length |\phi_k| \leq C for some constant C, in which case we simply brute force enumerate all O(2^C) possible truth value assignments for \phi_k. If \phi_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:

|\phi_1|^2 \leq |\phi|, |\phi_2|^2 \leq |\phi_1|, \dots, |\phi_k|^{2^k} \leq |\phi|

Thus, this requires k = O(\ln \ln |\phi|) iterations, and thus the whole algorithm runs in time \mathsf{poly}(|\phi|). The idea is similar to kernelization.

Step 4: Construct an H, such that H is polytime computable, H \to \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 \leq f(n).
  • For any \phi of length |\phi| < g(n), the Turing machine M_i correctly decides \phi \in \mathsf{SAT}^* with runtime \leq i|\phi|^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{poly}(n).

Claim: H(n) is well-defined and computable in \mathsf{poly}(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 \phi of length |\phi| \leq g(n), for i|\phi|^i \leq f(n) g(n)^{f(n)} steps. We also need to test whether \phi \in \mathsf{SAT}^*, 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)} 
\leq \mathsf{poly}(n)

Now, if SAT* is in P, then let M_m be a machine that decides SAT* in time Cn^{C'}. For sufficiently large n such that f(n) > \max(C, C', 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} \neq \mathsf{NP}.

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

References