Kolmogorov complexity, pseudorandom generators and statistical models testing

0411049 - UTIA-B 20030036 RIV CZ eng J - Článek v odborném periodiku
Šindelář, Jan - Boček, Pavel
Kolmogorov complexity, pseudorandom generators and statistical models testing.
Kybernetika. Roč. 38, č. 6 (2002), s. 747-759. ISSN 0023-5954
Grant CEP: GA ČR GA102/99/1564
Výzkumný záměr: CEZ:AV0Z1075907
Klíčová slova: Kolmogorov complexity * pseudorandom generators * statistical models testing
Kód oboru RIV: BB - Aplikovaná statistika, operační výzkum
Impakt faktor: 0.341, rok: 2002

An attempt to formalize heuristic concepts like strings (sequence 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. It is shown that no pseudorandom generator can produce long "typical" strings. The time complexity of pseudorandom generators with oracles capable to recognize "typical" strings is shown to be at least exponential with respect to the length of the output.
Trvalý link: http://hdl.handle.net/11104/0131136