Our website is made possible by displaying online advertisements to our visitors.
Please consider supporting us by disabling your ad blocker.
Incompressible string
 | This article needs additional citations for verification. (July 2019) |
An incompressible string is a string with Kolmogorov complexity equal to its length, so that it has no shorter encodings.[1] The pigeonhole principle can be used to be prove that for any lossless compression algorithm, there must exist many incompressible strings.
- ^ V. Chandru and M.R.Rao, Algorithms and Theory of Computation Handbook, CRC Press 1999, p29-30.
Previous Page Next Page
