Re: NP-Complete Definition

If C is the problem of searching a sorted array of N numbers for a
given number M, and if we pass to C, rather than an array of N
elements, a compressed .zip file containing the N elements compressed
to n^2 bits (where N = 2^n), with the guarantee that item at index i
can b extracted in polynomial time (with respect to n), then is C a
searching problem on the N numbers, or is C a different problem on the
n^2 bits.
What is the input size to C? N or n^2? We're not passing n^2 bits to
C, instead we have a "self-extracting" executable, metaphorically
speaking, which C queries as it would a disk or random access memory.
When C wants the number at index i, then the executable returns that
number. So C sees N numbers, but we have only n^2 bits.
Supposedly B is passed the compressed N numbers, and then R reduces B
to C while formulating a piece of code which can extract the number at
index i in polynomial time, in order to interface with C.
R can be polynomial because it doesn't have to pass each of the N
elements to C, it just provides a mechanism for C to access the
compressed N numbers that were passed to B (in the form of n^2 bits).
However C would be looking at an instance of N=2^n numbers, whereas B
received an input of size n.


tchow@xxxxxxxxxxxxx wrote:
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

.