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).
[1] One of the first uses of the incompressibility method with Kolmogorov complexity in the 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
[3] The method was applied to a number of fields, and its name was coined in a textbook.
Jacques Hadamard and Charles Jean de la Vallée-Poussin proved in 1896 that this number of primes is asymptotic to
, satisfies A more-sophisticated approach attributed to Piotr Berman (present proof partially by John Tromp) describes every incompressible
of each vertex satisfies To prove this by the incompressibility method, if the deviation is larger we can compress the description of
This theorem is required in a more complicated proof, where the incompressibility argument is used a number of times to show that the number of unlabeled graphs is A transitive tournament is a complete directed graph,
Since a tournament is a labeled, directed complete graph, it can be encoded by a string
[6] It is easily solved by the incompressibility method,[7] as are the coin-weighing problem, the number of covering families and expected properties; for example, at least a fraction of
[10] Using the incompressibility method, several versions of expanders and superconcentrator graphs were shown to exist.
This problem was solved for small arrangements, and much work was done on asymptotic expression as a function of
The general problem remains unsolved, apart from the best-known lower bound
This proves that for the overwhelming majority of the arrangements (and the expectation), the area of the smallest triangle formed by three of
In this case, the incompressibility method proves the lower and upper bounds of the property involved.
[12] The law of the iterated logarithm, the law of large numbers and the recurrence property were shown to hold using the incompressibility method[13] and Kolmogorov's zero–one law,[14] 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.
[15] 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.
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
A Turing-machine computation of a given word gives for each location (the boundary between adjacent cells) a sequence of crossings from left to right and right to left, each crossing in a particular state of the finite control.
Positions in the middle third of a candidate word all have a crossing sequence of length
Since the overwhelming majority of binary palindromes have a high Kolmogorov complexity, this gives a lower bound on the average-case running time.
More results concerning tapes, stacks and queues, deterministically and nondeterministically,[17] were proven with the incompressibility method.
[4] Heapsort is a sorting method, invented by J. W. J. Williams and refined by R. W. Floyd, which always runs in
It is questionable whether Floyd's method is better than Williams' on average, although it is better in the worst case.
The difficulty of analyzing the complexity of the sorting process is that it depends on the number
Although this sorting method inspired a large number of papers, only the worst case was established.
For the average running time, only the best case for a two-pass Shellsort[18] and an upper bound of
In every pass, the comparison sort moves a key to another place a certain distance (a path length).
[22] 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.
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.