Re: compression algorithm is NP complete problem?

jrefactors@xxxxxxxxxxx writes:

> I always want to understand more on practical applications of NP
> complete problem. My understanding of NP complete problem is that the
> problems cannot be solved in polynomial running time in deterministic
> machine. Correct?

No, that is as yet not known. NP means that the problem can be solved
in polynomial time on a nondeterministic Turing machine or,
equaivalently, that there exist a polynomial-size certificate for each
solution that will verify that this is a correct solution.

A problem is NP complete if every problem in NP can be transformed (in
polynomial time) into this problem. There is no statement about
minimum running times, but it is true that the best known algorithms
for NP complete problems may run in exponential time in the worst
case. But there is no theoretical reason that faster algorithms can't
exist.

> I heard someone say compression algorithm is NP complete problem. And
> different compression software such as Winzip, pkzip, etc.. compress
> the same file in different size, and there is no minimum size that can
> compress. I still don't understand how compression algorithm is NP
> complete problem.

Some compression problems can be stated as "given a simple unpacking
method, what is the shortest packed string that expands to the desired
string". If the unpacking method is in P, then the compression
problem is in NP, but not necessarily NP complete. Compression
methods are usually chosen so there exist a fast (usually near-linear)
compression algorithm. This may not necessarily give the shortest
possible packed string, though this is the case for many compression
algorithms (e.g., Huffman encoding).

The most general formulation of the compression problem is: Find the
smallest Turing machine that when running on an initially blank tape
eventually stops with the desired string on the tape. With this
formulation, the problem is actually undecidable. If you add time
limit to the Turing machines, e.g., requiring the number of steps to
be at most a*n^b, where n is the length of the output string, then the
problem is decidable and, for a fixed polynomial time limit it is in
NP (I believe).

Torben

.

Relevant Pages

  • Re: Attention Sean - question about CSI
    ... Maybe the degree of compression can serve as a measure ... What relation this would have to CSI ... If I am allowed to choose the compression algorithm *after* ... which compresses that string to a single bit. ...
    (talk.origins)
  • Re: Compression and crypto
    ... Now suppose that we have 64 possible compression algorithms, ... of trial decompression that's pretty conclusive evidence that ... That's the possibility that bijectivity eliminates. ... No compression algorithm is length-preserving. ...
    (sci.crypt)
  • Re: Attention Sean - question about CSI
    ... Maybe the degree of compression can serve as a measure ... If I am allowed to choose the compression algorithm *after* ... which compresses that string to a single bit. ... Yet, for a truly random sequence of numbers, you won't find any ...
    (talk.origins)
  • Re: Pi as the Mother Number
    ... Now suppose you run them through some sort of compression algorithm. ... The compression algorithm outputs a string of digits which you could ...
    (sci.math)
  • Re: Compression and crypto
    ... about which compression algorithm you chose). ... information to the compressed output. ... You have just beaten a perfect compressor whatever ...
    (sci.crypt)