Re: compression algorithm is NP complete problem?

From: "Denis Flex" <dnsflex___SPAM_CutThis___@xxxxxxxxx>
Date: Thu, 14 Apr 2005 09:30:49 GMT

> 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.

Oh yes!

.

References:
- compression algorithm is NP complete problem?
  - From: jrefactors
- Re: compression algorithm is NP complete problem?
  - From: Torben Ægidius Mogensen

Prev by Date: Re: compression algorithm is NP complete problem?
Next by Date: Computational Mathematics and Computer Science
Previous by thread: Re: compression algorithm is NP complete problem?
Next by thread: Re: compression algorithm is NP complete problem?
Index(es):
- Date
- Thread