Number of the records: 1
Kolmogorov complexity, pseudorandom generators and statistical models testing
- 1.
SYSNO ASEP 0411049 Document Type J - Journal Article R&D Document Type Journal Article Subsidiary J Ostatní články Title Kolmogorov complexity, pseudorandom generators and statistical models testing Author(s) Šindelář, Jan (UTIA-B)
Boček, Pavel (UTIA-B) RIDSource Title Kybernetika. - : Ústav teorie informace a automatizace AV ČR, v. v. i. - ISSN 0023-5954
Roč. 38, č. 6 (2002), s. 747-759Number of pages 13 s. Language eng - English Country CZ - Czech Republic Keywords Kolmogorov complexity ; pseudorandom generators ; statistical models testing Subject RIV BB - Applied Statistics, Operational Research R&D Projects GA102/99/1564 GA ČR - Czech Science Foundation (CSF) CEZ AV0Z1075907 - UTIA-B Annotation 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. Workplace Institute of Information Theory and Automation Contact Markéta Votavová, votavova@utia.cas.cz, Tel.: 266 052 201.
Number of the records: 1