Síla náhodných řetízků

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F06%3A00038960" target="_blank" >RIV/67985840:_____/06:00038960 - isvavai.cz</a>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Power from Random Strings

Popis výsledku v původním jazyce

We show that sets consisting of strings of high Kolmogorov comlexity provide examples of sets that are complete for several complexity classes under probabilistic and nonuniform reductions. These sets are provably not complete under the usual many-one reductions. Let R_C be the set of strings x having comlexity at least |x|2, according to the usual Kolmogorov complexity measure C. We show that R_C is hard for the class of recursive functions under P/poly-truth-table reductions. Furthermore, we show thatEXP is included in NP^{R_C}and PSPACE is in P^{R_C}. We also study resource bounded versions of Kolmogorov complexity and we show tighter results for the hardness and completeness of the sets of Kolmogorov random strings with respect to these measures.

Název v anglickém jazyce

Power from Random Strings

Popis výsledku anglicky

We show that sets consisting of strings of high Kolmogorov comlexity provide examples of sets that are complete for several complexity classes under probabilistic and nonuniform reductions. These sets are provably not complete under the usual many-one reductions. Let R_C be the set of strings x having comlexity at least |x|2, according to the usual Kolmogorov complexity measure C. We show that R_C is hard for the class of recursive functions under P/poly-truth-table reductions. Furthermore, we show thatEXP is included in NP^{R_C}and PSPACE is in P^{R_C}. We also study resource bounded versions of Kolmogorov complexity and we show tighter results for the hardness and completeness of the sets of Kolmogorov random strings with respect to these measures.

Druh

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

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

—

Návaznosti

Z - Vyzkumny zamer (s odkazem do CEZ)

Rok uplatnění

2006

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

Siam Journal on Computing

ISSN

0097-5397

e-ISSN

—

Svazek periodika

35

Číslo periodika v rámci svazku

6

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

27

Strana od-do

1467-1493

Kód UT WoS článku

—

EID výsledku v databázi Scopus

—