Status: Bibliographieeintrag
Standort: ---
Exemplare:
---
| Online-Ressource |
Verfasst von: | Ambos-Spies, Klaus [VerfasserIn]  |
| Terwijn, Sebastiaan A. [VerfasserIn]  |
| Zheng, Xizhong [VerfasserIn]  |
Titel: | Resource bounded randomness and weakly complete problems |
Verf.angabe: | Klaus Ambos-Spies, Sebastiaan A. Terwijn, Zheng Xizhong |
Jahr: | 1997 |
Umfang: | 13 S. |
Fussnoten: | Elektronische Reproduktion der Druck-Ausgabe 9. November 1999 ; Gesehen am 17.04.2023 |
Titel Quelle: | Enthalten in: Theoretical computer science |
Ort Quelle: | Amsterdam [u.a.] : Elsevier, 1975 |
Jahr Quelle: | 1997 |
Band/Heft Quelle: | 172(1997), 1, Seite 195-207 |
ISSN Quelle: | 1879-2294 |
Abstract: | We introduce and study resource bounded random sets based on Lutz's concept of resource bounded measure [7, 8]. 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 quantitative structure of E = DTIME(2lin). However, we will also comment on E2 = DTIME(2pol) and its corresponding (p2-) measure. 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 [2, 3]) and we show that nc + 1-random sets are nc-generic, whereas the converse fails. From the former we conclude that nc-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 nκ-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 [10]: 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. |
DOI: | doi:10.1016/S0304-3975(95)00260-X |
URL: | Bitte beachten Sie: Dies ist ein Bibliographieeintrag. Ein Volltextzugriff für Mitglieder der Universität besteht hier nur, falls für die entsprechende Zeitschrift/den entsprechenden Sammelband ein Abonnement besteht oder es sich um einen OpenAccess-Titel handelt.
Volltext: https://doi.org/10.1016/S0304-3975(95)00260-X |
| Volltext: https://www.sciencedirect.com/science/article/pii/S030439759500260X |
| DOI: https://doi.org/10.1016/S0304-3975(95)00260-X |
Datenträger: | Online-Ressource |
Sprache: | eng |
K10plus-PPN: | 184294181X |
Verknüpfungen: | → Zeitschrift |
Resource bounded randomness and weakly complete problems / Ambos-Spies, Klaus [VerfasserIn]; 1997 (Online-Ressource)
69066016