Co se dá efektivně zredukovat na Kolmogorovsky náhodné řetízky?

Kód výsledku v 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>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

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

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

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

Popis výsledku anglicky

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.

Druh

D - Stať ve sborníku

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

—

Návaznosti

Z - Vyzkumny zamer (s odkazem do CEZ)

Rok uplatnění

2004

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 statě ve sborníku

Proceedings 21st International Symposium on Theoretical Aspects of Computer Science (STACS)

ISBN

3-540-21236-1

ISSN

—

e-ISSN

—

Počet stran výsledku

12

Strana od-do

584-595

Název nakladatele

Springer-Verlag

Místo vydání

Berlin

Místo konání akce

Montpellier

Datum konání akce

25. 3. 2004

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—