Re: NP-Complete Definition

Thanks for the links Tim. Just to clarify, i'm aware that you can't
pass an arbitrary input of exponential size to a problem in polynomial
time.
The scenario i had in mind is one where B receives as input an already
"compressed list of numbers". There would be 2^n numbers compressed
into n^2 bits, so according to B's definition B's input size is n^2
bits (rather than the 2^n numbers). The list of 2^n numbers isn't
arbitrary. The 2^n numbers would follow a pattern (which enables them
to be compressed to n^2 bits).

The question i originally had is, what if, internally, B reduces to a
problem C on the 2^n numbers (which B received in compressed format)
in polynomial time. I'm aware that if B had to explicitely pass each
of the 2^n numbers out to C, then the reduction can't be performed in
polynomial time. What i was thinking is that since the 2^n numbers
(which B received in n^2 bits) follow a predictable pattern, B is able
to extract the ith item from the compressed bits in polynomial time.
And this seemed like a way to correctly reduce B to C in polynomial
time. In other words B would create a component which C can interface
with to obtain the ith element.

In practice we would probably use this reduction instead of passing
the the 2^n elements out explicitely to C, if possible.
For example, if C is the problem of searching a sorted array for a
number M, then C can be solved in O(log 2^n) = O(n). C only looks at
O(n) numbers,so by not passing the list of numbers explicitely (which
would take O(2^n)) but instead passing something which can extract the
ith number in poly time, and since C will only read O(n) numbers we're
able to solve B in O(n).

Maybe B should have been defined so that its input size is actually
2^n, rather than n^2, but typically we're free to define any problems
and their respective inputs, so it seemed to me that this scenario
might occur where problem B reduces to an instance C of a different
size in polynomial time, and then i saw the NP-Complete theorem which
doesn't restrict input size. But if Sipser assumes that the reduction
needs to pass input explicitely to C then this is not an issue. But
this seems a little fuzzy.

On Apr 30, 10:21 am, t...@xxxxxxxxxxxxx wrote:
In article <1177909226.449482.176...@xxxxxxxxxxxxxxxxxxxxxxxxxxx>,

<bobbysoa...@xxxxxxxxx> wrote:
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?

If you're passing the compressed file, then the input size to C is the size
of the compressed file.

However, when doing this kind of trick, you have to be careful of several
things.

1. P and NP are typically defined for *worst-case* complexity. So you have
to make sure that you can achieve your claimed exponential compression ratio
even in the *worst case*. For arbitrary files it isn't possible to achieve
this kind of compression ratio, though perhaps for carefully restricted
classes of input you might be able to do it.

2. You need to make sure that you're properly accounting for all the
operations involved. If the way you get the compressed file is to generate
the uncompressed file first and then compress it, then generating the
uncompressed file in the first place will take exponential time. Also the
self-extraction of the archive has to be accounted for in computing the
run-time of C, and so if the extraction process inadvertently extracts
2^n entries en route to the one you want, that will take exponential time.

Having said all that, I should say that the idea of exponentially succinct
representations is an important one, and you might be interested in the
following papers:

http://portal.acm.org/citation.cfm?id=116.120
http://portal.acm.org/citation.cfm?&id=10891
--
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


.

Relevant Pages

  • Re: Looking for a copy of TDLs ZASM
    ... HOW do I get the files out of the .lbr File ... Some archives are self extracting, ... One very good library extract program is called lbrext.com. ... current compression standards. ...
    (comp.os.cpm)
  • Re: uncompress files/or folders
    ... When you open a compressed folder, the 'Extract all files' command appears in the Folder Tasks list. ... If you're relying on compression to have enough free disk space, what you really need is a new hard disk. ...
    (microsoft.public.windowsxp.help_and_support)
  • BitZipper Archive Extraction Directory traversal
    ... BitZipper Archive Extraction Directory traversal ... compression and encoding formats with superior ... or TAR or ZIP or TAR.GZ or GZ ... Do not extract untrusted RAR and TAR and JAR and GZ ...
    (Bugtraq)
  • Re: CAB format
    ... Console Applcation" and a "Win32 Application". ... code for using cabinet.dll to extract from CABs. ... CABs, which turned out not to be so hard. ... compression method that can be used. ...
    (microsoft.public.vb.general.discussion)