Resource bounded randomness and weakly complete problems

• Verfasst von: Ambos-Spies, Klaus [VerfasserIn]
• Verfasst von: Terwijn, Sebastiaan A. [VerfasserIn]
• Verfasst von: Zheng, Xizhong [VerfasserIn]
• Titel: Resource bounded randomness and weakly complete problems
• Verf.angabe: Klaus Ambos-Spies, Sebastiaan A. Terwijn, Zheng Xizhong
• Jahr: 1994
• Umfang: 9 S.
• Fussnoten: Elektronische Reproduktion der Druck-Ausgabe 1. Januar 2005 ; Gesehen am 31.05.2023
• Titel Quelle: Enthalten in: Du, Dingzhu, 1948 - Algorithms and computation
• Ort Quelle: Berlin, Heidelberg : Springer Berlin Heidelberg, 1994
• Jahr Quelle: 1994
• Band/Heft Quelle: (1994), Seite 369-377
• ISBN Quelle: 978-3-540-48653-4
• DOI: doi:10.1007/3-540-58325-4_201
• Datenträger: Online-Ressource
• Sprache: eng
• K10plus-PPN: 1847037771

Abstract

We introduce and study resource bounded random sets based on Lutz's concept of resource bounded measure ([5, 6]). We concentrate on nc-randomness (c ≥ 2) which corresponds to the polynomial time bounded (p-) measure of Lutz, and which is adequate for studying the internal and quantative structure of E = DTIME(2lin). First we show that the class of nc-random sets has p-measure 1. This provides a new, simplified approach to p-measure 1-results. Next we compare randomness with genericity (in the sense of [1, 2]) and we show that nc+1-random sets are nc-generic, whereas the converse fails. From the former we conclude thatnc-random sets are not p-btt-complete for E. Our technical main results describe the distribution of the nc-random sets under p-m-reducibility. We show that every nc-random set in E has nk-random predecessors in E for any k ≥ 1, whereas the amount of randomness of the successors is bounded. We apply this result to answer a question raised by Lutz [8]: We show that the class of weakly complete sets has measure 1 in E and that there are weakly complete problems which are not p-btt-complete for E.