# Padding argument > Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Padding_argument > Markdown URL: https://mediated.wiki/source/Padding_argument.md > Source: https://en.wikipedia.org/wiki/Padding_argument > Source revision: 1355374329 > License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/) In [computational complexity theory](/source/Computational_complexity_theory), the **padding argument** is a tool to conditionally prove that if some [complexity classes](/source/Complexity_classes) are equal, then some other bigger classes are also equal. This type of argument is also sometimes used for [space complexity](/source/Space_complexity) classes, [alternating classes](/source/Alternation_(complexity)), and bounded alternating classes. ## Example ### EXP=NEXP **Theorem.** If [P](/source/P_(complexity)) = [NP](/source/NP_(complexity)) then [EXP](/source/EXP) = [NEXP](/source/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](/source/Non-deterministic_Turing_machine) *M* that verifies x\in L in nondeterministic time 2^{|x|^c}, for some constant [natural number](/source/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](/source/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](/source/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](/source/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](/source/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 - [Paddable language](/source/Paddable_language) - [NP-intermediate](/source/NP-intermediate) ## References - Arora, Sanjeev & Barak, Boaz (2009), [*Computational Complexity: A Modern Approach*](http://www.cs.princeton.edu/theory/complexity/), [Cambridge](/source/Cambridge_University_Press), p. 57, ISBN 978-0-521-42426-4 --- Adapted from the Wikipedia article [Padding argument](https://en.wikipedia.org/wiki/Padding_argument) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Padding_argument?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.