Power from Random Strings

0038960 - MÚ 2007 RIV US eng J - Článek v odborném periodiku
Allender, E. - Buhrman, H. - Koucký, Michal - van Melkebeek, D. - Ronneburger, D.
Power from Random Strings.
[Síla náhodných řetízků.]
Siam Journal on Computing. Roč. 35, č. 6 (2006), s. 1467-1493. ISSN 0097-5397. E-ISSN 1095-7111
Výzkumný záměr: CEZ:AV0Z10190503
Klíčová slova: Kolmogorov complexity * completeness * reductions
Kód oboru RIV: BA - Obecná matematika
Impakt faktor: 1.361, rok: 2006

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 that EXP 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.

Zkoumáme výpočetní sílu množiny Kolmogorovsky náhodných řetízků při použití jako orákulum.
Trvalý link: http://hdl.handle.net/11104/0133162