Kolmogorov complexity, pseudorandom generators and statistical models testing.

Kód výsledku v 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>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Kolmogorov complexity, pseudorandom generators and statistical models testing.

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Kolmogorov complexity, pseudorandom generators and statistical models testing.

Popis výsledku anglicky

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.

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

BB - Aplikovaná statistika, operační výzkum

OECD FORD obor

—

Projekt

<a href="/cs/project/GA102%2F99%2F1564" target="_blank" >GA102/99/1564: Centrum výzkumu a výuky adaptivních systémů: pilotní projekt</a><br>

Návaznosti

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

Rok uplatnění

2002

Kód důvěrnosti údajů

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

Název periodika

Kybernetika

ISSN

0023-5954

e-ISSN

—

Svazek periodika

38

Číslo periodika v rámci svazku

6

Stát vydavatele periodika

CZ - Česká republika

Počet stran výsledku

13

Strana od-do

747-759

Kód UT WoS článku

—

EID výsledku v databázi Scopus

—