Incompressibility Method

In mathematics, the incompressibility method is a proof method like the probabilistic method, the counting method or the pigeonhole principle. To prove that an object in a certain class (on average) satisfies a certain property, select an object of that class which is incompressible. If it does not satisfy the property, it can be compressed by computable coding. Since it can be generally proven that almost all objects in a given class are incompressible, the argument demonstrates that almost all objects in the class have the property involved (not just the average). To select an incompressible object is ineffective, and cannot be done by a computer program. However, a simple counting argument usually shows that almost all objects of a given class can be compressed by only a few bits (are incompressible).

The incompressibity method depends on an objective, fixed notion of incompressibility. Such a notion was provided by the Kolmogorov complexity theory, named for Andrey Kolmogorov.

The Kolmogorov complexity of an object, represented by a finite, binary string, is the length of the shortest binary program on a fixed, optimal universal Turing machine. Since the machine is fixed and the program concerned is the shortest, the Kolmogorov complexity is a definite positive integer. The Kolmogorov complexity of an object is the length of the shortest binary program from which it can be computed. Therefore, it is a lower bound on the length of a computably-compressed version (in bits) of that object by any existing (or future) compression program.

One of the first uses of the incompressibility method with Kolmogorov complexity its theory of computation was to prove that the running time of a one-tape Turing machine is quadratic for accepting a palindromic language and sorting algorithms require at least ${\displaystyle n\log n}$ time to sort ${\displaystyle n}$ items. The first influential paper using the incompressibility method was published in 1980. The method was applied to a number of fields, and its name was coined in a textbook.

...
Wikipedia