Počet záznamů: 1
Derandomizing from random strings
- 1.
SYSNO ASEP 0352483 Druh ASEP C - Konferenční příspěvek (mezinárodní konf.) Zařazení RIV D - Článek ve sborníku Název Derandomizing from random strings Tvůrce(i) Buhrman, H. (NL)
Fortnow, L. (US)
Koucký, Michal (MU-W) RID, SAI, ORCID
Loff, B. (PT)Zdroj.dok. Proceedings of the 25th Annual IEEE Conference on Computational Complexity, CCC 2010. - Los Alamitos : IEEE Computer Society 2010, 2010 - ISBN 978-0-7695-4060-3 Rozsah stran s. 58-63 Poč.str. 6 s. Akce 25th Annual IEEE Conference on Computational Complexity, CCC 2010 Datum konání 09.06.2010-12.06.2010 Místo konání Cambridge Země US - Spojené státy americké Typ akce WRD Jazyk dok. eng - angličtina Země vyd. US - Spojené státy americké Klíč. slova Kolmogorov random strings ; reducibility ; complexity classes Vědní obor RIV BA - Obecná matematika CEP GAP202/10/0854 GA ČR - Grantová agentura ČR IAA100190902 GA AV ČR - Akademie věd 1M0545 GA MŠMT - Ministerstvo školství, mládeže a tělovýchovy CEZ AV0Z10190503 - MU-W (2005-2011) UT WOS 000286932700007 EID SCOPUS 77955259331 DOI 10.1109/CCC.2010.15 Anotace In this paper we show that BPP is truth-table reducible to the set of Kolmogorov random strings R_K. It was previously known that PSPACE, and hence BPP is Turing-reducible to R_K. The earlier proof relied on the adaptivity of the Turing-reduction to find a Kolmogorov-random string of polynomial length using the set R_K as oracle. Our new non-adaptive result relies on a new fundamental fact about the set R_K, namely each initial segment of the characteristic sequence of $R_K$ has high Kolmogorov complexity. As a partial converse to our claim we show that strings of very high Kolmogorov-complexity when used as advice are not much more useful than randomly chosen strings. Pracoviště Matematický ústav Kontakt Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757 Rok sběru 2011
Počet záznamů: 1