소개글
kolmogorov complexity에 대한 전반적인 소개와 응용에 대해 작성하였습니다.
목차
1 Introduction: What is Algorithmic Infor-
mation Theory?
2 Kolmogorov Complexity
2.1 Properties of Kolmogorov Complexity
2.2 Motivation
3 Where is it being used?
3.1 Communication Complexity
3.2 Minimal Description Length and Minimal Message
Length
4 Conclusion
References
본문내용
4 Conclusion
It is interesting that Kolmogorov Compelxity is connected to randomness
and compression. It tells us that the perfect randomness cannot be achieved
with a seed lesser than the length of the string which is quite intuitive if we
think back.
Let`s say we decided to
ip a coin ten times in turn with a friend. He goes
rst and tells us that the result is \HHHHHHHHHH". Most of us would think
something`s wrong and would as \How is that possible?", then the friend
says, \All the outcomes are independent and equally likely. It is one of the
outcomes, so here it is". We understand that theoretically it is possible but
something is doubtable. Then why do we think that it is less likely then other
outcomes when they all have the same probability? As we have discussed
in previous parts, the outcome \HHHHHHHHHH" has very low complexity.
Kolmogorov complexity of this string is less than length of it. However,
outcomes such as \THTTHHHTHT" has Kolmogorov complexity of almost
its length since it is not compressible. We can say it is random. That`s why
the latter seems more likely.
참고 자료
Yossi Borenstein and Riccardo Poli, Kolmogorov complexity, optimiza-
tion and hardness, 2006.
Rudi Cilibrasi and Paul M. B. Vitanyi, Clustering by compression, CoRR
cs.CV/0312044 (2003).
Alexander Gammerman and V. Vovk, Kolmogorov complexity: Sources,
theory and applications, The Computer Journal 42 (1999), 252{255.
Peter Grunwald and Paul Vitanyi, Shannon Information and Kol-
mogorov Complexity, October 2004.
Peter D. Grunwald and Paul M. B. Vitanyi, Algorithmic information
theory, CoRR abs/0809.2754 (2008).
Vaclav Hlavac, Keith G. Jeery, and Jir Wiedermann (eds.), Sofsem
2000: Theory and practice of informatics, 27th conference on current
trends in theory and practice of informatics, milovy, czech republic,
november 25 - december 2, 2000, proceedings, Lecture Notes in Computer
Science, vol. 1963, Springer, 2000.
Marcus Hutter, The fastest and shortest algorithm for all well-dened
problems, International Journal of Foundations of Computer Science 13
(2002), no. 3, 431{443.
Ming Li and Paul M.B. Vitnyi, An introduction to kolmogorov complexity
and its applications, 3 ed., Springer Publishing Company, Incorporated,
2008.
Austin Mohr, Quantum computing in complexity theory and theory of
computation.
Paul M. B. Vitanyi (ed.), Computational learning theory, second euro-
pean conference, eurocolt `95, barcelona, spain, march 13-15, 1995, pro-
ceedings, Lecture Notes in Computer Science, vol. 904, Springer, 1995.
C. S. Wallace and D. L. Dowe, Minimum message length and kolmogorov
complexity, Computer Journal 42 (1999), 270{283.