DocumentCode
3359756
Title
Combinatorics and Kolmogorov complexity
Author
Li, Ming ; Vitányi, Paul M B
Author_Institution
Dept. of Comput. Sci., Waterloo Univ., Ont., Canada
fYear
1991
fDate
30 Jun-3 Jul 1991
Firstpage
154
Lastpage
163
Abstract
The authors investigate combinatorial properties of finite sequences with high Kolmogorov complexity. They also demonstrate the utility of a Kolmogorov complexity method in combinatorial theory by several examples (such as the coin-weighing problem)
Keywords
combinatorial mathematics; computational complexity; Kolmogorov complexity; coin-weighing problem; combinatorial theory; finite sequences; Binary sequences; Combinatorial mathematics; Computer science; Frequency; H infinity control; Information theory; Machinery; Random processes; Random sequences; Random variables;
fLanguage
English
Publisher
ieee
Conference_Titel
Structure in Complexity Theory Conference, 1991., Proceedings of the Sixth Annual
Conference_Location
Chicago, IL
Print_ISBN
0-8186-2255-5
Type
conf
DOI
10.1109/SCT.1991.160256
Filename
160256
Link To Document