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).
Contents
History
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
Number theory
According to an elegant Euclidian proof, there is an infinite number of prime numbers. Bernhard Riemann demonstrated that the number of primes less than a given number is connected with the 0s of the Riemann zeta function. Jacques Hadamard and Charles Jean de la Vallée-Poussin proved in 1896 that this number of primes is asymptotic to
A more-sophisticated approach attributed to Piotr Berman (present proof partially by John Tromp) describes every incompressible
Both proofs are presented in more detail.
Graph theory
A labeled graph
To prove this by the incompressibity method, if the deviation is larger we can compress the description of
Combinatorics
A transitive tournament is a complete directed graph,
This was shown as the first problem. It is easily solved by the incompressibility method, as are the coin-weighing problem, the number of covering families and expected properties; for example, at least a fraction of
If a number of events are independent (in probability theory) of one another, the probability that none of the events occur can be easily calculated. If the events are dependent, the problem becomes difficult. Lovász local lemma is a principle that if events are mostly independent of one another and have an individually-small probability, there is a positive probability that none of them will occur. It was proven by the incompressibility method. Using the incompressibility method, several versions of expanders and superconcentrator graphs were shown to exist.
Topological combinatorics
In the Heilbronn triangle problem, throw
Probability
The law of the iterated logarithm, the law of large numbers and the recurrence property were shown to hold using the incompressibility method and Kolmogorov's zero-one law, with normal numbers expressed as binary strings (in the sense of E. Borel) and the distribution of 0s and 1s in binary strings of high Kolmogorov complexity.
Turing-machine time complexity
The basic Turing machine, as conceived by Alan Turing in 1936, consists of a memory: a tape of potentially-infinite cells on which a symbol can be written and a finite control, with a read-write head attached, which scans a cell on the tape. At each step, the read-write head can change the symbol in the cell being scanned and move one cell left, right, or not at all according to instruction from the finite control. Turing machines with two tape symbols may be considered for convenience, but this is not essential.
In 1968, F. C. Hennie showed that such a Turing machine requires order
If other palindromes (ending in an accepting state on the left) have the same crossing sequence, the word (consisting of a prefix up to the position of the involved crossing sequence) of the original palindome concatenated with a suffix the remaining length of the other palindrome would be accepted as well. Taking the palindrome of
Since the overwhelming majority of binary palindromes have a high Kolmogorov complexity, this gives a lower bound on the average-case running time. The result is much more difficult, and shows that Turing machines with
In 1984, W. Maass and M. Li and P. M. B. Vitanyi showed that the simulation of two work tapes by one work tape of a Turing machine takes
Theory of computation
Heapsort is a sorting method, invented by J. W. J. Williams and refined by R. W. Floyd, which always runs in
Shellsort, discovered by Donald Shell in 1959, is a comparison sort which divides a list to be sorted into sublists and sorts them separately. The sorted sublists are then merged, reconstituting a partially-sorted list. This process repeats a number of times (the number of passes). The difficulty of analyzing the complexity of the sorting process is that it depends on the number
Logic
According to Gödel's first incompleteness theorem, in every formal system with computably enumerable theorems (or proofs) strong enough to contain Peano arithmetic, there are true (but unprovable) statements or theorems. This is proved by the incompressibility method; every formal system
Comparison with other methods
Although the probabilistic method generally shows the existence of an object with a certain property in a class, the incompressibility method tends to show that the overwhelming majority of objects in the class (the average, or the expectation) have that property. It is sometimes easy to turn a probabilistic proof into an incompressibility proof or vice versa. In some cases, it is difficult or impossible to turn a proof by incompressibility into a probabilistic (or counting proof). In virtually all the cases of Turing-machine time complexity cited above, the incompressibility method solved problems which had been open for decades; no other proofs are known. Sometimes a proof by incompressibility can be turned into a proof by counting, as happened in the case of the general lower bound on the running time of Shellsort.