I came across the following theorem in Sipser's about incompressible strings.

Let $\;f$ be some computable function which holds for almost all strings. The for any $b > 0 $, the property $\;f$ is false only on finitely many strings that are incompressible by $b\;$.

where "almost all strings" means that as $n$ grows the fraction of strings of length $n$ for which $f$ is false approaches $0$.

The book proves the above theorem and says that if we select some sufficiently long string at random, it's likely that property $f$ would hold true for it. Thus incompressible strings and random strings share this property.

Though I understand the proof for the theorem, I am unable to understand its meaning. How does this show there is some sort of relation between incompressible strings and random strings?

Also how does this theorem help us? Although I can generate random strings, there is no method to generate incompressible strings in general.

  • $\begingroup$ what section is that? ps in some sense if you understand the proof then you understand the meaning. :) $\endgroup$ – vzn Nov 26 '15 at 20:38

The theorem says, in effect, that incompressible strings are a deterministic model of random strings. If you have some property that you can prove using random strings, you can also prove it using incompressible strings instead. If you have some construction involving a random string, you can make it somewhat more explicit using an incompressible string.

Another deterministic model of randomness, which is very useful in theoretical computer science, is expanders. These are models of random graphs with respect to a lot of properties. In many cases, instead of using a random graph you can use an expander. Since we can construct expanders explicitly, this allows us to derandomize many randomized constructions.

While the same cannot be said for incompressible strings, they are useful in some circumstances. Their use in lower bounds is known as the incompressibility method, which I encourage you to look up.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.