<p>I see the padding arguments in terms of compactness of representation.  Think of two translator Turing machines: $B$ blows up instances, and $C$ compresses them again.</p>

<p>The padding argument works with $B$, by composing $B$ with the deterministic version of the TM for the language in the lower nondeterministic class.  The outputs of $B$ collectively form a language which is not compactly represented, so this becomes "easier".</p>

<p>It isn't possible to apply the idea the other way, using $C$, because only some of the languages in the easy class are generated by blowing up languages in the hard class.</p>



CC BY-SA 2.5
2010-10-24T14:00:49.157Z
2010-10-24T14:00:49.157Z
András Salamon
<p>OK, so your goal is to show that $CLASS_1[g(f(n))] = CLASS_2[h(f(n))]$ basing on $CLASS_1[g(n)] = CLASS_2[h(n)]$ (we don't specify what exactly are this classes, we just know that they're somehow parametrized with the input size). We have a language $L \in CLASS_1[g(f(n))]$, decided by some algorithm $A$. Now we make a language $L'$ by padding each word in $x \in L$, so that it's length is now $f(n)$, and we see that it is contained in $CLASS_1[g(n)]$ (our new algorithm $A'$ basically just ignores the added zeroes and runs $A$ on the real, short input). </p>

<p>What we do is: <em>we take a language from the bigger class and we pad it, so that it can be solved by a weaker algorithm giving us containment in the smaller class - the weaker algorithm can do it, because it has the same amount of 'real work' to do as before, but it has its restrictions (being a function of the input length) lifted by extending the input.</em></p>

<p>Now we know that $L' \in CLASS_1[g(n)]$ and hence  $L' \in CLASS_2[h(n)]$ (decided by some algorithm $B'$). We would like to get from here to $L \in CLASS_2[h(f(n))]$. But that is straightforward - algorithm $B$ deciding $L$ just pads the input accordingly and runs $B'$ on the padded input. </p>

<p>This step may be summarized as follows: <em>we want to decide $L$ in the bigger, more resourceful class. Using our extra resources we pad the input and run the algorithm deciding the padded language</em>.</p>

<p>Of course there are some technical detailes involved here (f.e. we have to make sure that the padding can be implemented in the classes we consider) but I just ignore them to give the general intuition.</p>

CC BY-SA 2.5
2010-10-24T09:38:01.463Z
2010-10-24T09:38:01.463Z
Karolina Sołtys
<p>To make it more intuitive lets look at what is going on more abstractly!</p>
<p>We have two transformations, one for inputs and one for problems.I will denote both of them by <span class="math-container">$pad$</span>, it will be clear from the context when it is the first one and when it is the second one.</p>
<p>These two transformations have the following property:</p>
<blockquote>
<p>I. for all problems <span class="math-container">$A\subseteq \Sigma^{ * } $</span>, for all inputs <span class="math-container">$x\in\Sigma^{ * } $</span>:</p>
<p><span class="math-container">$pad(x) \in pad(A)$</span> iff <span class="math-container">$x \in A$</span>,</p>
<p>II. if <span class="math-container">$A$</span> is in <span class="math-container">$EXP$</span> (<span class="math-container">$NEXP$</span>), then <span class="math-container">$pad(A)$</span> is in <span class="math-container">$P$</span> (<span class="math-container">$NP$</span>).</p>
<p>III. the transformation for inputs is in complexity class <span class="math-container">$EXP$</span>,</p>
</blockquote>
<p>It is clear that the transformations for padding have these properties.</p>
<p>Now, the reason that we don't know how to do the same thing in the reverse direction is that we don't have transformations like padding in the reverse direction (when we exchange <span class="math-container">$EXP$</span> with <span class="math-container">$P$</span> and <span class="math-container">$NEXP$</span> with <span class="math-container">$NP$</span>). So the question is why?</p>
<p>I don't have a formal argument why there are not such transformations at the moment, but intuitively what András Salamon said is correct. It is easy to increase the size of inputs, but it is not clear how they can be compressed?</p>
<p>Another way to understand it is to think about in the following way. Assume that <span class="math-container">$P=NP$</span>, and we want to solve an <span class="math-container">$NEXP=NTime(2^{n^{O(1)}})$</span> problem. We are given an input <span class="math-container">$x$</span> of length <span class="math-container">$n$</span>, we <em>think</em> of it as an input of length <span class="math-container">$N=2^{n^{O(1)}}$</span>:</p>
<blockquote>
<p><span class="math-container">$NEXP(n) = NTime(2^{n^{O(1)}}) = NTime(N) \subseteq NP(N) \subseteq P(N) = Time(N^{O(1)}) = Time(2^{n^{O(1)}}) = EXP(n)$</span></p>
</blockquote>

CC BY-SA 2.5
2010-10-25T03:54:04.867Z
the latter argument, which I see as a kind of "transformation of variables" argument has occurred to me. However, i don't see why you can't just "think" of it having an input of say, $ N=log(n) $ thus translating it down. I don't think that quite works, though the two other approaches, to think of it in terms of giving more resources to a NP algorithm, and in terms of compression vs padding makes sense.
gabgoh
CC BY-SA 2.5
2010-10-25T04:02:10.740Z
A third way to think of it, actually, is to look at the converse. I've not followed through that approach to the bitter end but if any great insight comes I'll post it as a response to myself.
gabgoh
CC BY-SA 2.5
2010-10-25T04:25:18.973Z
@gabgoh: It is more delicate than just change of variables. I am *thinking* of the input as being of length $N=2^{n^{O(1)}}$, this works because $n\leq N$, I just imagine that there are enough blanks at the end of the original input to make the length equal to $N$, but how can you think of an input of length $n$ as being of length $N=\log(n)$? Don't forget that what is inside the parenthesis is the length of the input! i.e. that is the part of the input that the output of the function is going to depend on.
Kaveh
CC BY-SA 2.5
2010-10-25T04:31:45.817Z
[continued] Considering this might also help: assume that the input is in unary and of length $n$, then we can compress it to $N = \lceil \log(n) \rceil$ bits and actually that would work! A problem which is $P$ ($NP$) with unary encoding will be in $EXP$ ($NEXP$) with binary encoding.
Kaveh
CC BY-SA 2.5
2010-10-25T04:48:51.987Z
I guess my trouble is with the phrase "thinking of", I can't wrap my head around what it means to think of a smaller input as a larger input, and what that does, in reality. I do realize that you can't think of $N=log(n)$, for the reason you state, which is a restatement of the padding argument, not a clean analogy I suppose. After all, when we change variables we are always thinking of variables in terms of other variables, but unlike real variables it's kinda "incompressible". Not to say it is a bad answer, but it doesn't help me much personally.
gabgoh
CC BY-SA 2.5
2010-10-25T04:54:48.237Z
@Kaveh: Actually, I just saw your second example, and it is helpful! It does put in concrete terms what this whole "compression" thing is about. I wonder if this has anything to do with Kolmogoro@v complexity and the incompressibility of strings.
gabgoh
CC BY-SA 2.5
2010-10-25T05:01:00.753Z
@gabgoh: The "thinking of" argument can also be made formal, and at the end all of these are essentially the same thing. The way to formalized it is as follows: What is the input length? It is the part that the output of the machine is going to depend on, we usually define it as the number of characters on the tape before the first blank, but do we need to? Can't we just define it as being $2^n$ where $n$ is as before? And when we have defined what is the length of a given input, that is all what informal phrase "thinking of" is saying. We can completely formalized this argument.
Kaveh
CC BY-SA 2.5
2010-10-25T05:05:07.940Z
Another example similar to the unary case is by changing what is the set of inputs. In place of $\Sigma^{ * }$, assume that we allow only very very sparse strings as possible inputs to our TMs. Then it would be possible to compress them even more using binary strings! And as long as we can compress the inputs (while staying in the required complexity class) we can prove similar results in the reverse direction. It is all about the representations used for inputs and how we define their length.
Kaveh
CC BY-SA 2.5
2010-11-16T04:12:34.730Z
I am copying it from a comment by JeffE because I think it is relevant and interesting: If $NP=DTIME(n^{\log n})$, then $P\neq NP$ but $EXP = NEXP$.
Kaveh
CC BY-SA 2.5
2010-10-25T00:15:44.127Z
2010-10-25T04:48:50.280Z
2020-06-17T09:38:08.363Z
Kaveh
<p>I think the best way to get intuition for this issue is to think of what the complete problems for exponential time classes are.  For example, the complete problems for NE are the standard NP-complete problems on succinctly describable inputs, e.g., given a circuit that describes the adjacency matrix of a graph, is the graph 3-colorable?  Then the problem of
whether E=NE becomes equivalent to whether NP problems are solvable in polynomial time on the
succinctly describable inputs, e.g., those with small effective Kolmogorov complexity.   This is obviously no stronger than whether they are solvable on all inputs.  The larger the time bound, the smaller the Kolmogorov complexity of the relevant inputs, so collapses for larger time bounds are in effect algorithms that work on smaller subsets of inputs.</p>

<p>Russell Impagliazzo</p>

CC BY-SA 2.5
2010-10-25T06:00:26.243Z
2010-10-25T06:00:26.243Z
Russell Impagliazzo
<p>Hey Guys, I understand that the padding trick allows us to translate complexity classes upwards - for example $P=NP \rightarrow EXP=NEXP$. Padding works by "inflating" the input, running the conversion (say from say $NP$ to $P$), which yields a "magic" algorithm which you can run on the padded input. While this makes technical sense, I can't get a good intuition of how this works. What exactly is going on here? Is there a simple analogy for what padding is? </p>

<p>Can provide a <em>common sense</em> reason why this is the case? </p>

CC BY-SA 2.5
2010-10-24T14:45:00.977Z
I'd like to point out that not all complexity class results go upwards. For example, if you proved $EXP \neq NEXP$, then that would imply $P \neq NP$. In general, collapses go up, while separations go down.
Robin Kothari
CC BY-SA 2.5
2010-10-24T20:06:34.083Z
indeed. In fact, this seems like a good way to think about it, as separations are more intuitive than collapses.
gabgoh
CC BY-SA 2.5
2010-10-25T06:39:50.153Z
@Robin, @gabgoh: even some collapses go downwards, but not by padding arguments.  See for example http://arxiv.org/abs/cs/9910008.
Joshua Grochow
<cc.complexity-theory><complexity-classes><padding>
Why do equalities between complexity classes translate upwards and not downwards?
gabgoh
# Why do equalities between complexity classes translate upwards and not downwards?

(Asked by: username_0 on 2010-10-24)

Hey Guys, I understand that the padding trick allows us to translate complexity classes upwards - for example $P=NP \rightarrow EXP=NEXP$. Padding works by "inflating" the input, running the conversion (say from say $NP$ to $P$), which yields a "magic" algorithm which you can run on the padded input. While this makes technical sense, I can't get a good intuition of how this works. What exactly is going on here? Is there a simple analogy for what padding is?

Can provide a *common sense* reason why this is the case?

**Tags:** cc.complexity-theory, complexity-classes, padding
> **Comments:**
> **username_1**: I'd like to point out that not all complexity class results go upwards. For example, if you proved $EXP \neq NEXP$, then that would imply $P \neq NP$. In general, collapses go up, while separations go down.  
> **username_0**: indeed. In fact, this seems like a good way to think about it, as separations are more intuitive than collapses.  
> **username_2**: @Robin, @gabgoh: even some collapses go downwards, but not by padding arguments.  See for example http://arxiv.org/abs/cs/9910008.  

---

## 4 answers

### Answer by username_6 on 2010-10-25. Score: 30 | Accepted answer

I think the best way to get intuition for this issue is to think of what the complete problems for exponential time classes are. For example, the complete problems for NE are the standard NP-complete problems on succinctly describable inputs, e.g., given a circuit that describes the adjacency matrix of a graph, is the graph 3-colorable? Then the problem of
whether E=NE becomes equivalent to whether NP problems are solvable in polynomial time on the
succinctly describable inputs, e.g., those with small effective Kolmogorov complexity. This is obviously no stronger than whether they are solvable on all inputs. The larger the time bound, the smaller the Kolmogorov complexity of the relevant inputs, so collapses for larger time bounds are in effect algorithms that work on smaller subsets of inputs.

Russell Impagliazzo


---

### Answer by username_4 on 2010-10-24. Score: 15

OK, so your goal is to show that $CLASS\_1[g(f(n))] = CLASS\_2[h(f(n))]$ basing on $CLASS\_1[g(n)] = CLASS\_2[h(n)]$ (we don't specify what exactly are this classes, we just know that they're somehow parametrized with the input size). We have a language $L \in CLASS\_1[g(f(n))]$, decided by some algorithm $A$. Now we make a language $L'$ by padding each word in $x \in L$, so that it's length is now $f(n)$, and we see that it is contained in $CLASS\_1[g(n)]$ (our new algorithm $A'$ basically just ignores the added zeroes and runs $A$ on the real, short input).

What we do is: *we take a language from the bigger class and we pad it, so that it can be solved by a weaker algorithm giving us containment in the smaller class - the weaker algorithm can do it, because it has the same amount of 'real work' to do as before, but it has its restrictions (being a function of the input length) lifted by extending the input.*

Now we know that $L' \in CLASS\_1[g(n)]$ and hence $L' \in CLASS\_2[h(n)]$ (decided by some algorithm $B'$). We would like to get from here to $L \in CLASS\_2[h(f(n))]$. But that is straightforward - algorithm $B$ deciding $L$ just pads the input accordingly and runs $B'$ on the padded input.

This step may be summarized as follows: *we want to decide $L$ in the bigger, more resourceful class. Using our extra resources we pad the input and run the algorithm deciding the padded language*.

Of course there are some technical detailes involved here (f.e. we have to make sure that the padding can be implemented in the classes we consider) but I just ignore them to give the general intuition.


---

### Answer by username_3 on 2010-10-24. Score: 13

I see the padding arguments in terms of compactness of representation. Think of two translator Turing machines: $B$ blows up instances, and $C$ compresses them again.

The padding argument works with $B$, by composing $B$ with the deterministic version of the TM for the language in the lower nondeterministic class. The outputs of $B$ collectively form a language which is not compactly represented, so this becomes "easier".

It isn't possible to apply the idea the other way, using $C$, because only some of the languages in the easy class are generated by blowing up languages in the hard class.


---

### Answer by username_5 on 2010-10-25. Score: 5

To make it more intuitive lets look at what is going on more abstractly!

We have two transformations, one for inputs and one for problems.I will denote both of them by $pad$, it will be clear from the context when it is the first one and when it is the second one.

These two transformations have the following property:

> I. for all problems $A\subseteq \Sigma^{ \* } $, for all inputs $x\in\Sigma^{ \* } $:
>
> $pad(x) \in pad(A)$ iff $x \in A$,
>
> II. if $A$ is in $EXP$ ($NEXP$), then $pad(A)$ is in $P$ ($NP$).
>
> III. the transformation for inputs is in complexity class $EXP$,

It is clear that the transformations for padding have these properties.

Now, the reason that we don't know how to do the same thing in the reverse direction is that we don't have transformations like padding in the reverse direction (when we exchange $EXP$ with $P$ and $NEXP$ with $NP$). So the question is why?

I don't have a formal argument why there are not such transformations at the moment, but intuitively what András Salamon said is correct. It is easy to increase the size of inputs, but it is not clear how they can be compressed?

Another way to understand it is to think about in the following way. Assume that $P=NP$, and we want to solve an $NEXP=NTime(2^{n^{O(1)}})$ problem. We are given an input $x$ of length $n$, we *think* of it as an input of length $N=2^{n^{O(1)}}$:

> $NEXP(n) = NTime(2^{n^{O(1)}}) = NTime(N) \subseteq NP(N) \subseteq P(N) = Time(N^{O(1)}) = Time(2^{n^{O(1)}}) = EXP(n)$

> **Comments:**
> **username_0**: the latter argument, which I see as a kind of "transformation of variables" argument has occurred to me. However, i don't see why you can't just "think" of it having an input of say, $ N=log(n) $ thus translating it down. I don't think that quite works, though the two other approaches, to think of it in terms of giving more resources to a NP algorithm, and in terms of compression vs padding makes sense.  
> **username_0**: A third way to think of it, actually, is to look at the converse. I've not followed through that approach to the bitter end but if any great insight comes I'll post it as a response to myself.  
> **username_5**: @gabgoh: It is more delicate than just change of variables. I am *thinking* of the input as being of length $N=2^{n^{O(1)}}$, this works because $n\leq N$, I just imagine that there are enough blanks at the end of the original input to make the length equal to $N$, but how can you think of an input of length $n$ as being of length $N=\log(n)$? Don't forget that what is inside the parenthesis is the length of the input! i.e. that is the part of the input that the output of the function is going to depend on.  
> **username_5**: [continued] Considering this might also help: assume that the input is in unary and of length $n$, then we can compress it to $N = \lceil \log(n) \rceil$ bits and actually that would work! A problem which is $P$ ($NP$) with unary encoding will be in $EXP$ ($NEXP$) with binary encoding.  
> **username_0**: I guess my trouble is with the phrase "thinking of", I can't wrap my head around what it means to think of a smaller input as a larger input, and what that does, in reality. I do realize that you can't think of $N=log(n)$, for the reason you state, which is a restatement of the padding argument, not a clean analogy I suppose. After all, when we change variables we are always thinking of variables in terms of other variables, but unlike real variables it's kinda "incompressible". Not to say it is a bad answer, but it doesn't help me much personally.  
> **username_0**: @Kaveh: Actually, I just saw your second example, and it is helpful! It does put in concrete terms what this whole "compression" thing is about. I wonder if this has anything to do with Kolmogoro@v complexity and the incompressibility of strings.  
> **username_5**: @gabgoh: The "thinking of" argument can also be made formal, and at the end all of these are essentially the same thing. The way to formalized it is as follows: What is the input length? It is the part that the output of the machine is going to depend on, we usually define it as the number of characters on the tape before the first blank, but do we need to? Can't we just define it as being $2^n$ where $n$ is as before? And when we have defined what is the length of a given input, that is all what informal phrase "thinking of" is saying. We can completely formalized this argument.  
> **username_5**: Another example similar to the unary case is by changing what is the set of inputs. In place of $\Sigma^{ * }$, assume that we allow only very very sparse strings as possible inputs to our TMs. Then it would be possible to compress them even more using binary strings! And as long as we can compress the inputs (while staying in the required complexity class) we can prove similar results in the reverse direction. It is all about the representations used for inputs and how we define their length.  
> **username_5**: I am copying it from a comment by JeffE because I think it is relevant and interesting: If $NP=DTIME(n^{\log n})$, then $P\neq NP$ but $EXP = NEXP$.  

---

