Page 1

Displaying 1 – 2 of 2

Showing per page

Kolmogorov complexity and probability measures

Jan Šindelář, Pavel Boček (2002)

Kybernetika

Classes of strings (infinite sequences resp.) with a specific flow of Kolmogorov complexity are introduced. Namely, lower bounds of Kolmogorov complexity are prescribed to strings (initial segments of infinite sequences resp.) of specified lengths. Dependence of probabilities of the classes on lower bounds of Kolmogorov complexity is the main theme of the paper. Conditions are found under which the probabilities of the classes of the strings are close to one. Similarly, conditions are derived under...

Kolmogorov complexity, pseudorandom generators and statistical models testing

Jan Šindelář, Pavel Boček (2002)

Kybernetika

An attempt to formalize heuristic concepts like strings (sequences resp.) “typical” for a probability measure is stated in the paper. Both generating and testing of such strings is considered. Kolmogorov complexity theory is used as a tool. Classes of strings “typical” for a given probability measure are introduced. It is shown that no pseudorandom generator can produce long strings from the classes. The time complexity of pseudorandom generators with oracles capable to recognize “typical” strings...

Currently displaying 1 – 2 of 2

Page 1