25
$\begingroup$

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?

$\endgroup$
  • 11
    $\begingroup$ 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. $\endgroup$ – Robin Kothari Oct 24 '10 at 14:45
  • $\begingroup$ indeed. In fact, this seems like a good way to think about it, as separations are more intuitive than collapses. $\endgroup$ – gabgoh Oct 24 '10 at 20:06
  • 2
    $\begingroup$ @Robin, @gabgoh: even some collapses go downwards, but not by padding arguments. See for example arxiv.org/abs/cs/9910008. $\endgroup$ – Joshua Grochow Oct 25 '10 at 6:39
30
$\begingroup$

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

$\endgroup$
14
$\begingroup$

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.

$\endgroup$
13
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – gabgoh Oct 25 '10 at 3:54
  • 1
    $\begingroup$ 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. $\endgroup$ – gabgoh Oct 25 '10 at 4:02
  • 1
    $\begingroup$ @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. $\endgroup$ – Kaveh Oct 25 '10 at 4:25
  • 1
    $\begingroup$ [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. $\endgroup$ – Kaveh Oct 25 '10 at 4:31
  • 1
    $\begingroup$ 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. $\endgroup$ – gabgoh Oct 25 '10 at 4:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.