Power from Random Strings

Result code in 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>
Result on the web
—
DOI - Digital Object Identifier
—

Result language
angličtina
Original language name
Power from Random Strings
Original language description
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.
Czech name
Síla náhodných řetízků
Czech description
Zkoumáme výpočetní sílu množiny Kolmogorovsky náhodných řetízků při použití jako orákulum.

Type
J<sub>x</sub> - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
BA - General mathematics
OECD FORD branch
—

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

Similar results(10)