**Address GIF preview for sharing:****https://dragif.com/pdf/aZjq**- PDF file size:
- 234.56 kB
- Source:
**Queensu.ca****Free PDF file download:****Download: complexity.pdf**- Date saved:
- April 6, 2017

In computer science, the concepts of algorithm and information are fundamental. So the

measurement of information or algorithms is crucial in sense of describing. In 1965

Andrey Nikolaevich Kolmogorov [O'Connor, and Robertson, 1999sian

mathematician, established the algorithmic theory of randomness via a measure of

complexity, now referred to Kolmogorov complexity. According to Kolmogorov, the

complexity of an object is the length of the shortest computer program that can reproduce

the object. All algorithms can be expressed in programming language based on Turing

machine models equally succinctly, up to a fixed additive constant term. The remarkable

usefulness and inherent rightness of the theory of Kolmogorov complexity or so called

Descriptive complexity, stems from this independence of the description method.

The idea of Kolmogorov complexity first appeard in the 1960’s in papers by

Kolmogorov, Solomonoff and Chaitin. As specified by Schöning and Randall, an

algorithm can exhibit very different complexity behavior in the worst case and in the

average case. The Kolmogorov complexity is defined a probability distribution under

which worst-case and average-case running time (for all algorithm simultaneously) are

the same (up to constant factors). Quick sort algorithm has been widely taken as an

example to show the applicability of Kolmogorov complexity since the algorithm takes

) time at worst case. Later, the Kolmogorov

complexity was connected with Information Theory and proved to be closely related to

Claude Shannon's entropy rate of an information source. The theory base of Kolmogorov

complexity has also be extended to data compression and communication for the sake of

true information measure.

We will briefly take a look at Kolmogorov Complexity definition and some main related

results at this section. For details, please refer to [Cover and Thomas, 1991

Definition: The Kolmogorov Complexity Ku(x) of a string x with respect to a universal

computer U is defined as:

the minimum length over all programs that print x and halt. Thus Ku(x) is the shortest

description length of x over all descriptions interpreted by computer U. (Note Turing

machine is regarded as universal computer in computer science.)

The concept of Kolmogorov Complexity asks for the minimal unambiguous

description of a sequence. It can be used to prove complexity lower bounds. [Schöning

ples of using this technique. And indeed, as mentioned,

the proofs obtained in this way are much more “elegant”, or at least shorter, than the

original proofs. In a few cases, the lower bounds were first achieved by means of

Kolmogorov Complexity. Another quite important definition is the conditional

Kolmogorov complexity which is based on the knowledge of the length of x, denoted as

l(x).

3 This is the shortest description length if the computer U has the length of x made

available to it. Quite a few different results have been shown for conditional Kolmogorov

complexity too.

We look at some basic and interesting properties of Kolmogorov complexity and

then consider some examples. The proofs of the theorems are eliminated because of the

purpose of this report. However, for your interests, please refer to [Cover and Thomas,

1991] for complete proofs.

Both the lower and upper bounds of Kolmogorov complexity of a given sequence

have been derived early. There are some choices of both bounds from different aspects.

The followings are all established theorems for bounds.

Universality of Kolmogorov complexity: If U is a universal computer, then for any other

for all string x ∈ {0, 1}*, where the constant c

not depend on x.

Conditional complexity is less than the length of sequence: Ku(x| l(x)) ≤ l(x)+ c.

Upper bound on Kolmogorov complexity: Ku(x) ≤ Ku(x| l(x)) + 2log (l(x)) + c.

Lower bound on Kolmogorov complexity: The number of strings x with complexity

Ku(x) ≤ k satisfies: |{ x ∈ {0, 1}*: Ku(x) ≤ k } | < 2

The Kolmogorov complexity of a binary string x is bounded by:

(p) = -p log p – (1-p) log (1-p) is the binary entropy function.

4 The above five theorems are basically considered to be very important facts of

Kolmogorov complexity. Many other interesting results have been derived applying these

theorems. We consider some examples of Kolmogorov complexity here to show the

usability of the theory with its properties. First, we will look at some intuitive ideas

directly coming from the definition. A sequence of n zeros has a constant Kolmogorov

complexity, i.e. K(000…0|n) = c, since if we assume n is known, the a short program can

directly print out n zeros. The same case can be applied to

πcan be calculated using a simple series expression. A somewhat surprising result for

fractal is that regarding its complex calculations, it is still essentially very simple in terms

of Kolmogorov complexity which is nearly zero. An integer on the other hand, has higher

complexity even it looks very straight forward. It is obviously true that the complexity of

describing an integer will be constant if we know the length of the integer, i.e. K(n|l(n)) =

c. However, in general, the computer does not know the length of binary representation

of the integer. So we must inform the computer in some way when the description ends.

We can bound the description using the upper bound we got so far: K(n) ≤ 2log n + c.

We can also prove there are an infinite number of integers n such that K(n) > log n. This

is probably less intuitive than we thought. From above examples, it is not hard to see the

true measurement of information or algorithm would be rather hard without the

development of Kolmogorov complexity. With the support of the Kolmogorov

complexity theory, one can describe information more accurate in computer science.

Kolmogorov complexity also applied to algorithmically random, incompressible

sequences, the halting problem, etc. We can not go into details of those examples; instead,

we briefly look at those problems here just to get some taste. Many literatures have been

5 published on Kolmogorov complexity related questions. One can refer to [Li, and Vitanyi,

1999eading. The algorithmically random and

incompressible sequences are defined based on the Kolmogorov complexity properties

that some sequences hold. We say a sequence x

| n) ≥ n. And we can say a string x incompressible if lim K(x

1. The definitions seem very intuitive with respect of Kolmogorov complexity. In fact, if

every element of the sequence is completely generated in random, we can not predict any

later elements from current. Indeed, we will need to describe each element separately.

However, if the Kolmogorov complexity verse n approaching 1 for a string in probability,

then we can actually interpret this as the proportions of 0’s and 1’s in this string are

almost equal, which is ½. By this meaning, it is true that we can not compress the string

since any bit will be a critical contribution to the whole, which also specifies the

randomness of the string. The next significant application is on the halting problem.

Using Kolmogorov complexity, we can actually demonstrate that the problem can not be

solved by an algorithm because of the non-computability of Kolmogorov complexity. It

is rather a surprising fact of the non-computability. However, practically speaking, one

may never be able to tell the shortest program since there are infinite many programs for

a given sequence. We can only estimate the complexity by running more and more

programs, as we know the bound will converge to the Kolmogorov complexity. Many

other results can also be found on published literatures related with probability theory and

information theory. At the following section, we take a look at one of the most important

results related with the central idea of information theory – Entropy.

As mentioned at introduction, the Kolmogorov complexity and entropy of a sequence of

random variables are highly related. In general, the expected value of the Kolmogorov

complexity of a random sequence is to its entropy.

From information theory founded by Shannon, the true measure of information on

random variables is entropy. This relationship actually proves the correctness of the

Kolmogorov complexity as a measurement of information and algorithms. Kolmogorov

complexity states the shortest description (program) for a random variable. Then

complexity of the sequence constructed by random variables will approach to the expect

value of the set of Kolmogorov complexities for each variable, i.e. E[1/nK(X

supported by the law of large numbers in probability. Respectively, the information

measure of the sequence is indeed entropy. Actually, one can always show the program

lengths satisfy prefix condition, since if the computer halts on any program, it does not

look any further for input. The relationship can be shown further with Kraft inequality.

The relationship provides us to two ways of complexity measures, which either

takes after Kolmogorov complexity, involving finding some computer or abstract

automaton which will produce the pattern of interest, or take after information theory and

produce something like the entropy, which, while in principle computable, can be very

hard to calculate reliably for experimental systems. This is actually very powerful

principle in physics (see [Li, and Vitanyi, 1999ore interesting idea

about “Occam’s Razor” as a general principle governing scientific research can be

derived from Kolmogorov theory as we will see at the next section.

I decide to include this topic mainly because its importance plus the idea really amazed

me. At 14th century, William of Occam (Ockham in some literatures), a logician, said

“Nunquam ponenda est pluralitas sine necessitate”, i.e., explanations should not be

multiplied beyond necessity, which forms the basis of methodological reductionism. Here,

our argument will be a special case of it.

Recent papers have suggested a connection between Occam's Razor and

Kolmogorov complexity. Many literatures take Laplace’s sun rising problem as an

example to explain the connection. Laplace considered the probability that the sun will

rise again tomorrow, given that it has risen every day in recorded history. He solved it

before Kolmogorov complexity was introduced. However, the problem can be

reconsidered through Kolmogorov complexity. If we use 1 to represent the sun rise, then

the probability that the next symbol is a 1 given n 1’s in the sequence so far is: ∑

) = c > 0. And the probability that the next symbol is 0, which means that

of n with length at least K(n), i.e. about log n + O(log log n). Hence the conditional

probability of observing a 0 next is: p(0|1

result is very similar to 1/(n+1) derived by Laplace. The Kolmogorv complexity solution

to this question is actually following the Occam’s Razor by weighting possible

explanations by their complexity.

It often happens that the best explanation is much more complicated than the

simplest possible explanation because it requires fewer assumptions. Albert Einstein

8 wrote in 1933 “Theories should be as simple as possible, but no simpler.” In our case,

Kolmogorov complexity does provide us an alternative approach to explain things in

many science fields.

Kolmogorov complexity is a profound theory for information and algorithm measure.

The theory is somehow different from others that we have studied in computational

complexity so far. I feel the theory tries to observe the complexity from a new approach.

It is worth reading something about Kolmogorov [O'Connor, and Robertson, 1999

understand his original idea, which he developed from mathematical perspective. It is in

high level of abstraction, but closely related with many things in practice. Vladimir

V’yugin presents some applications of Kolmogorov complexity in his review [V’yugin,

puting, I found many ongoing topics related with

Kolmogorov complexity are on information process ([Levin, 1999

Dowe, 1999a]). Generally, the application of Kolmogorv complexity is based on

framework of the Minimum Description Length (MDL) principle and Minimum Message

Length (MML) principle, which are out the scope of this report, but refer to [Wallace, and

Dowe, 1999b] for introductions.

I strongly believe the Kolmogorov complexity should have more appearances in

future research topics. Along with information theories, we need to deal with information

as well as problems coming with it. Like the Shannon’s entropy theory established

today’s communication system, the closely related Kolmogorov complexity shall also be

of great potential to be applied to future researches.

Cover, M. Thomas, and Thomas, A. Joy. Elements of information theory. John Wiley &

Sons, Inc. 1991.

Gammerman, Alexander, and Vovk, Vladimir. Kolmogorov complexity: sources, theory

and applications. The Computer Journal, vol. 42, no. 4, 1999.

Levin, A. Leonid. Robust Measures of Information. The Computer Journal, vol. 42, no. 4,

1999.

Li, Ming, and Vitanyi, Paul. An Introduction to Kolmogorov Complexity and Its

Applications. Springer-Verlag, New York, 1999.

O'Connor, J J, and Robertson, E F. “Andrey Nikolaevich Kolmogorov”. School of

Mathematics and Statistics, University of St. Andrews, Scotland, 1999.

Rissanen, Jorma. Discussion of paper `Minimum Message Length and Kolmogorov

Complexity' by C. S. Wallace and D. L. Dowe. The Computer Journal, vol. 42, no. 4,

1999.

Schöning, Uwe, and Pruim, Randall. Gems of theoretical computer science. Springer-

Verlag Berlin Heidelberg 1998.

PDF file: http://research.cs.queensu.ca/home/xiao/doc/complexity.pdf

© 2024 PERPETUM

info@dragif.com

**DraGIF.com** - easy and effective way to share PDF on Facebook

Příroda.cz • Bejvavalo.cz • aterliér Hapík.cz • Pieris.cz