compression algorithm is NP complete problem?

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?

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.


Please advise. thanks!!

.

Relevant Pages

  • 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: Compression and crypto
    ... about which compression algorithm you chose). ... information to the compressed output. ... You have just beaten a perfect compressor whatever ...
    (sci.crypt)
  • Re: compression algorithm is NP complete problem?
    ... polynomial time) into this problem. ... > I heard someone say compression algorithm is NP complete problem. ... I still don't understand how compression algorithm is NP ... what is the shortest packed string that expands to the desired ...
    (comp.theory)
  • Re: DASD Compression Question
    ... compressing "may foul up the compression algorithm" did not ... with just 'DASD Compression' for search argument. ... For IBM-MAIN subscribe / signoff / archive access instructions, ... send email to listserv@xxxxxxxxxxx with the message: GET IBM-MAIN INFO ...
    (bit.listserv.ibm-main)