Skip to main content
Theoretical Computer Science

You are not logged in. Your edit will be placed in a queue until it is peer reviewed.

We welcome edits that make the post easier to understand and more valuable for readers. Because community members review edits, please try to make the post substantially better than how you found it, for example, by fixing grammar or adding additional resources and hyperlinks.

Required fields*

9
  • 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$ Commented Oct 25, 2010 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$ Commented Oct 25, 2010 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$ Commented Oct 25, 2010 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$ Commented Oct 25, 2010 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$ Commented Oct 25, 2010 at 4:48