Re: NP-Complete Definition

In article <1177900082.165788.59570@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
<bobbysoares@xxxxxxxxx> wrote:
Maybe the original input to B was of size n, and after applying the
reduction we are left to solve C with an input of size 2^n.
The reduction occurs in polynomial time

This is impossible, for the simple reason that the time taken to write down
an output of exponential size is exponential. You can't write down more
than one character per time step.

The reduction can't pass all subsets to C in polynomial time, because
there's too many subsets, but it can pass to C something which is able
to access each of the subsets, which is just as good as far as C is
concerned.
So B is reduced to C in polynomial time, but the input size changed
substantially. Would we classify C as NP Complete based on this?

If the input to C is actually polynomial in size and was produced in
polynomial time, then that's fine. It doesn't matter if there is some
sense in which there are "implicitly" exponentially many possibilities
hidden in the polynomially-size output. A lot of what computers do,
after all, is draw out information that is implicit and make it explicit!

The way to get it straight is to remember that C has to be handed
*something* explicitly. Is that "something" polynomial in size? If so,
then that works fine. If not, if it's exponential, then it must have
taken exponential time to produce, and it's illegal in this context.
--
Tim Chow tchow-at-alum-dot-mit-dot-edu
The range of our projectiles---even ... the artillery---however great, will
never exceed four of those miles of which as many thousand separate us from
the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences
.