Kolmogorov complexity, pseudorandom generators and statistical models testing.

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985556%3A_____%2F02%3A16030036" target="_blank" >RIV/67985556:_____/02:16030036 - isvavai.cz</a>

Result on the web

—

DOI - Digital Object Identifier

—

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

—

Type

J_x - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)

CEP classification

BB - Applied statistics, operational research

OECD FORD branch

—

Project

<a href="/en/project/GA102%2F99%2F1564" target="_blank" >GA102/99/1564: Research and education centre in adaptive systems - A pilot project</a><br>

Continuities

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>Z - Vyzkumny zamer (s odkazem do CEZ)

Publication year

2002

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

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

—