View source for Nivedyam

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 (complexity)|P]]&nbsp;=&nbsp;[[NP (complexity)|NP]] implies [[EXP]]&nbsp;=&nbsp;[[NEXP]] uses "padding". <math>EXP \subseteq NEXP</math> by definition, so it suffices to show <math>NEXP \subseteq EXP</math>. 

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 <math>2^{n^c}</math> for some constant ''c''.  Let 

: <math>L'=\{x1^{2^{|x|^c}} \mid x \in L\},</math>
 
where ''1'' is a symbol not occurring in ''L''.  First we show that <math>L'</math> is in ''NP'', then we will use the deterministic polynomial time machine given by ''P''&nbsp;=&nbsp;''NP'' to show that ''L'' is in ''EXP''.

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

The <math>1^d</math> 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
| last2=Barak | first2=Boaz
| title=Computational Complexity: A Modern Approach
| url = http://www.cs.princeton.edu/theory/complexity/
| publisher=[[Cambridge University Press|Cambridge]]
| year=2009
| isbn=978-0-521-42426-4
| page = 57
}}

{{comp-sci-theory-stub}}
{{DEFAULTSORT:Computational Complexity Theory}}
[[Category:Computational complexity theory|*]]