Why do equalities between complexity classes translate upwards and not downwards?

Question

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?

Answer 1

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 2

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 3

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 4

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)$