Kolmogorov complexity, pseudorandom generators and statistical models testing.
Result description
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.
Keywords
Kolmogorov complexitypseudorandom generatorsstatistical models testing
The result's identifiers
Result code in IS VaVaI
Result on the web
—
DOI - Digital Object Identifier
—
Alternative languages
Result language
angličtina
Original language name
Kolmogorov complexity, pseudorandom generators and statistical models testing.
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
Jx - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
BB - Applied statistics, operational research
OECD FORD branch
—
Result continuities
Project
GA102/99/1564: Research and education centre in adaptive systems - A pilot project
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Z - Vyzkumny zamer (s odkazem do CEZ)
Others
Publication year
2002
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
Kybernetika
ISSN
0023-5954
e-ISSN
—
Volume of the periodical
38
Issue of the periodical within the volume
6
Country of publishing house
CZ - CZECH REPUBLIC
Number of pages
13
Pages from-to
747-759
UT code for WoS article
—
EID of the result in the Scopus database
—
Basic information
Result type
Jx - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP
BB - Applied statistics, operational research
Year of implementation
2002