Padding argument

---

title: "Padding argument" type: doc version: 1 created: 2026-02-28 author: "Wikipedia contributors" status: active scope: public tags: ["computational-complexity-theory"] description: "Proof technique in computational complexity theory" topic_path: "technology/computing" source: "https://en.wikipedia.org/wiki/Padding_argument" license: "CC BY-SA 4.0" wikipedia_page_id: 0 wikipedia_revision_id: 0

::summary 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.

Example

The proof that P = NP implies EXP = NEXP uses "padding".

\mathrm{EXP} \subseteq \mathrm{NEXP} by definition, so it suffices to show \mathrm{NEXP} \subseteq \mathrm{EXP}.

Let L be a language in NEXP. Since L is in NEXP, there is a non-deterministic Turing machine M that decides L in time 2^{n^c} for some constant c. Let

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

where '1' is a symbol not occurring in L. First we show that L' is in NP, then we will use the deterministic polynomial time machine given by P = NP to show that L is in EXP.

L' can be decided in non-deterministic polynomial time as follows. Given input x', verify that it has the form x' = x1^{2^{|x|^c}} and reject if it does not. If it has the correct form, simulate M(x). The simulation takes non-deterministic 2^{|x|^c} time, which is polynomial in the size of the input, x'. So, L' is in NP. By the assumption P = NP, there is also a deterministic machine DM that decides L' in polynomial time. We can then decide L in deterministic exponential time as follows. Given input x, simulate DM(x1^{2^{|x|^c}}). This takes only exponential time in the size of the input, x.

The 1^d is called the "padding" of the language L. This type of argument is also sometimes used for space complexity classes, alternating classes, and bounded alternating classes.

References

• {{Citation | last1=Arora | first1=Sanjeev | authorlink1=Sanjeev Arora (computer scientist) | last2=Barak | first2=Boaz|author2link = Boaz Barak | title=Computational Complexity: A Modern Approach | url = http://www.cs.princeton.edu/theory/complexity/ | publisher=Cambridge | year=2009 | isbn=978-0-521-42426-4 | page = 57 ::callout[type=info title="Wikipedia Source"] This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page. ::