Re: NP-Complete Definition

In article <1177909226.449482.176250@xxxxxxxxxxxxxxxxxxxxxxxxxxx>,
<bobbysoares@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: [PATCH 3/5] Add support for LZO-compressed kernels
    ... The lzo compressor is worse than gzip at compression, ... So for a compression ratio that is still relatively close to gzip, ... Is that "time to run the extraction algorithm", or "time to read in image from ...
    (Linux-Kernel)
  • Re: Analyse of PDF (or EPS?)
    ... > It depends on the type of images (bitmap vs. vector). ... Yes I know - but the vector based images should be extracted just as it ... some of the other compression techniques may be less accessible. ... > documents, including basic text extraction, but I've become pretty disillusioned ...
    (comp.lang.python)
  • Re: ZIP
    ... Use phrases like: ... visual basic zip compression ... visual basic zip extraction ... good luck! ...
    (microsoft.public.vb.general.discussion)