What Can Be Efficiently Reduced to the K-random Strings?

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F06%3A00038951" target="_blank" >RIV/67985840:_____/06:00038951 - isvavai.cz</a>
Result on the web
—
DOI - Digital Object Identifier
—

Result language
angličtina
Original language name
What Can Be Efficiently Reduced to the K-random Strings?
Original language description
We investigate the question of whether one can characterize complexity classes ( such as PSPACE or NEXP ) in terms of efficient reducibility to the set of Kolmogorov-random strings R_C. We show that this question cannot be posed without explicitly dealing with issues raised by the choice of universal machine in the definition of Kolmogorov complexity. Among other results, we show that although for every universal machine U, there are very complex sets that are poly-time dtt-reducible to R_{C_U}, it is nonetheless true that P=the set of all decidable sets in the intersection, over all universal machines U, of the sets that are poly-time dtt-reducible to R_{C_U|. We also show for a broad class of reductions that the sets reducible to R_C have small circuit complexity.
Czech name
Co se dá efektivně zredukovat na Kolmogorovsky náhodné řetízky?
Czech description
Studujeme, jak výpočetně složité množiny se dají redukovat na množinu Kolmogorovsky náhodných řetízků.

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)