Resource bounded randomness and weakly complete problems
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 structu...
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Dokumenttyp: | Kapitel/Artikel |
| Sprache: | Englisch |
| Veröffentlicht: |
1994
|
| In: |
Algorithms and computation
Year: 1994, Pages: 369-377 |
| DOI: | 10.1007/3-540-58325-4_201 |
| Online-Zugang: | Verlag: https://dx.doi.org/10.1007/3-540-58325-4_201
|
| Verfasserangaben: | Klaus Ambos-Spies, Sebastiaan A. Terwijn, Zheng Xizhong |
MARC
| LEADER | 00000caa a2200000 c 4500 | ||
|---|---|---|---|
| 001 | 1847037771 | ||
| 003 | DE-627 | ||
| 005 | 20230710182404.0 | ||
| 007 | cr uuu---uuuuu | ||
| 008 | 230531s1994 xx |||||o 00| ||eng c | ||
| 024 | 7 | |a 10.1007/3-540-58325-4_201 |2 doi | |
| 035 | |a (DE-627)1847037771 | ||
| 035 | |a (DE-599)KXP1847037771 | ||
| 035 | |a (OCoLC)1389826621 | ||
| 040 | |a DE-627 |b ger |c DE-627 |e rda | ||
| 041 | |a eng | ||
| 084 | |a 28 |2 sdnb | ||
| 100 | 1 | |a Ambos-Spies, Klaus |d 1951- |e VerfasserIn |0 (DE-588)141551607 |0 (DE-627)629951861 |0 (DE-576)16006810X |4 aut | |
| 245 | 1 | 0 | |a Resource bounded randomness and weakly complete problems |c Klaus Ambos-Spies, Sebastiaan A. Terwijn, Zheng Xizhong |
| 264 | 1 | |c 1994 | |
| 300 | |a 9 | ||
| 336 | |a Text |b txt |2 rdacontent | ||
| 337 | |a Computermedien |b c |2 rdamedia | ||
| 338 | |a Online-Ressource |b cr |2 rdacarrier | ||
| 500 | |a Elektronische Reproduktion der Druck-Ausgabe 1. Januar 2005 | ||
| 500 | |a Gesehen am 31.05.2023 | ||
| 520 | |a 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. | ||
| 700 | 1 | |a Terwijn, Sebastiaan A. |e VerfasserIn |0 (DE-588)140769552 |0 (DE-627)703782266 |0 (DE-576)320698742 |4 aut | |
| 700 | 1 | |a Zheng, Xizhong |e VerfasserIn |0 (DE-588)1286451906 |0 (DE-627)1843052164 |4 aut | |
| 773 | 0 | 8 | |i Enthalten in |a Du, Dingzhu, 1948 - |t Algorithms and computation |d Berlin, Heidelberg : Springer Berlin Heidelberg, 1994 |g (1994), Seite 369-377 |h Online-Ressource |w (DE-627)1649308841 |w (DE-576)322907128 |z 9783540486534 |7 nnam |
| 773 | 1 | 8 | |g year:1994 |g pages:369-377 |g extent:9 |a Resource bounded randomness and weakly complete problems |
| 856 | 4 | 0 | |u https://dx.doi.org/10.1007/3-540-58325-4_201 |x Verlag |
| 951 | |a AR | ||
| 992 | |a 20230531 | ||
| 993 | |a BookComponentPart | ||
| 994 | |a 1994 | ||
| 998 | |g 141551607 |a Ambos-Spies, Klaus |m 141551607:Ambos-Spies, Klaus |d 110000 |d 110300 |e 110000PA141551607 |e 110300PA141551607 |k 0/110000/ |k 1/110000/110300/ |p 1 |x j | ||
| 999 | |a KXP-PPN1847037771 |e 4327625310 | ||
| BIB | |a Y | ||
| JSO | |a {"type":{"bibl":"chapter","media":"Online-Ressource"},"note":["Elektronische Reproduktion der Druck-Ausgabe 1. Januar 2005","Gesehen am 31.05.2023"],"language":["eng"],"recId":"1847037771","person":[{"given":"Klaus","family":"Ambos-Spies","role":"aut","roleDisplay":"VerfasserIn","display":"Ambos-Spies, Klaus"},{"display":"Terwijn, Sebastiaan A.","roleDisplay":"VerfasserIn","role":"aut","family":"Terwijn","given":"Sebastiaan A."},{"role":"aut","display":"Zheng, Xizhong","roleDisplay":"VerfasserIn","given":"Xizhong","family":"Zheng"}],"title":[{"title_sort":"Resource bounded randomness and weakly complete problems","title":"Resource bounded randomness and weakly complete problems"}],"physDesc":[{"extent":"9 S."}],"relHost":[{"origin":[{"publisherPlace":"Berlin, Heidelberg","dateIssuedDisp":"1994","publisher":"Springer Berlin Heidelberg","dateIssuedKey":"1994"}],"id":{"isbn":["9783540486534"],"eki":["1649308841"],"doi":["10.1007/3-540-58325-4"]},"name":{"displayForm":["by Ding-Zhu Du, Xiang-Sun Zhang"]},"relMultPart":[{"disp":"Lecture Notes in Computer Science","note":["Gesehen am 28.02.20","Das Gesamtwerk gliedert sich in: Lecture notes in artificial intelligence; Lecture notes in bioinformatics"],"type":{"bibl":"serial","media":"Online-Ressource"},"language":["eng"],"recId":"316228877","pubHistory":["1.1973 -"],"part":{"number_sort":["834"],"number":["834"]},"titleAlt":[{"title":"LNCS online"},{"title":"LNAI"},{"title":"Lecture notes in artificial intelligence"},{"title":"Lecture notes in bioinformatics"},{"title":"LNAI"},{"title":"LNBI"},{"title":"LNCS-LNAI"},{"title":"LNCS-LNBI"}],"title":[{"title_sort":"Lecture notes in computer science","title":"Lecture notes in computer science"}],"physDesc":[{"extent":"Online-Ressource"}],"dispAlt":"Lecture notes in computer science","origin":[{"dateIssuedDisp":"1973-","publisher":"Springer","dateIssuedKey":"1973","publisherPlace":"Berlin ; Heidelberg"}],"id":{"eki":["316228877"],"zdb":["2018930-8"],"issn":["1611-3349"]}}],"physDesc":[{"extent":"Online-Ressource"}],"title":[{"title_sort":"Algorithms and computation","subtitle":"5th International Symposium, ISAAC '94, Beijing, P.R. China, August 25 - 27, 1994 : proceedings","title":"Algorithms and computation"}],"person":[{"family":"Du","given":"Dingzhu","display":"Du, Dingzhu","role":"aut"},{"family":"Zhang","given":"Xiang-Sun","display":"Zhang, Xiang-Sun","role":"oth"}],"part":{"extent":"9","text":"(1994), Seite 369-377","pages":"369-377","year":"1994"},"type":{"bibl":"book","media":"Online-Ressource"},"disp":"Du, Dingzhu, 1948 - Algorithms and computation","language":["eng"],"recId":"1649308841"}],"name":{"displayForm":["Klaus Ambos-Spies, Sebastiaan A. Terwijn, Zheng Xizhong"]},"origin":[{"dateIssuedDisp":"1994","dateIssuedKey":"1994"}],"id":{"doi":["10.1007/3-540-58325-4_201"],"eki":["1847037771"]}} | ||
| SRT | |a AMBOSSPIESRESOURCEBO1994 | ||