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_____%2F04%3A00038949" target="_blank" >RIV/67985840:_____/04:00038949 - 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 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ů.

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

Article name in the collection
Proceedings 21st International Symposium on Theoretical Aspects of Computer Science (STACS)
ISBN
3-540-21236-1
ISSN
—
e-ISSN
—
Number of pages
12
Pages from-to
584-595
Publisher name
Springer-Verlag
Place of publication
Berlin
Event location
Montpellier
Event date
Mar 25, 2004
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—

Similar results(10)