Cover Image

Resource bounded randomness and weakly complete problems

Show other versions (1)

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 structu...

Full description

Saved in:
Bibliographic Details
Main Authors: Ambos-Spies, Klaus (Author) , Terwijn, Sebastiaan A. (Author) , Zheng, Xizhong (Author)
Format: Article (Journal)
Language:English
Published: 1997
In: Theoretical computer science
Year: 1997, Volume: 172, Issue: 1, Pages: 195-207
ISSN:1879-2294
DOI:10.1016/S0304-3975(95)00260-X
Online Access:Verlag, lizenzpflichtig, Volltext: https://doi.org/10.1016/S0304-3975(95)00260-X
Verlag, lizenzpflichtig, Volltext: https://www.sciencedirect.com/science/article/pii/S030439759500260X
Get full text
Author Notes:Klaus Ambos-Spies, Sebastiaan A. Terwijn, Zheng Xizhong

MARC

LEADER 00000caa a2200000 c 4500
001 184294181X
003 DE-627
005 20230710175502.0
007 cr uuu---uuuuu
008 230417s1997 xx |||||o 00| ||eng c
024 7 |a 10.1016/S0304-3975(95)00260-X  |2 doi 
035 |a (DE-627)184294181X 
035 |a (DE-599)KXP184294181X 
035 |a (OCoLC)1389825964 
040 |a DE-627  |b ger  |c DE-627  |e rda 
041 |a eng 
084 |a 27  |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 1997 
300 |a 13 
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 9. November 1999 
500 |a Gesehen am 17.04.2023 
520 |a 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. 
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  |t Theoretical computer science  |d Amsterdam [u.a.] : Elsevier, 1975  |g 172(1997), 1, Seite 195-207  |h Online-Ressource  |w (DE-627)265784174  |w (DE-600)1466347-8  |w (DE-576)074891030  |x 1879-2294  |7 nnas  |a Resource bounded randomness and weakly complete problems 
773 1 8 |g volume:172  |g year:1997  |g number:1  |g pages:195-207  |g extent:13  |a Resource bounded randomness and weakly complete problems 
856 4 0 |u https://doi.org/10.1016/S0304-3975(95)00260-X  |x Verlag  |x Resolving-System  |z lizenzpflichtig  |3 Volltext 
856 4 0 |u https://www.sciencedirect.com/science/article/pii/S030439759500260X  |x Verlag  |z lizenzpflichtig  |3 Volltext 
951 |a AR 
992 |a 20230417 
993 |a Article 
994 |a 1997 
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-PPN184294181X  |e 4309384579 
BIB |a Y 
SER |a journal 
JSO |a {"title":[{"title":"Resource bounded randomness and weakly complete problems","title_sort":"Resource bounded randomness and weakly complete problems"}],"person":[{"given":"Klaus","family":"Ambos-Spies","role":"aut","roleDisplay":"VerfasserIn","display":"Ambos-Spies, Klaus"},{"given":"Sebastiaan A.","family":"Terwijn","role":"aut","roleDisplay":"VerfasserIn","display":"Terwijn, Sebastiaan A."},{"role":"aut","roleDisplay":"VerfasserIn","display":"Zheng, Xizhong","given":"Xizhong","family":"Zheng"}],"language":["eng"],"recId":"184294181X","type":{"media":"Online-Ressource","bibl":"article-journal"},"note":["Elektronische Reproduktion der Druck-Ausgabe 9. November 1999","Gesehen am 17.04.2023"],"id":{"doi":["10.1016/S0304-3975(95)00260-X"],"eki":["184294181X"]},"origin":[{"dateIssuedDisp":"1997","dateIssuedKey":"1997"}],"name":{"displayForm":["Klaus Ambos-Spies, Sebastiaan A. Terwijn, Zheng Xizhong"]},"relHost":[{"origin":[{"publisher":"Elsevier","dateIssuedKey":"1975","dateIssuedDisp":"1975-","publisherPlace":"Amsterdam [u.a.]"}],"id":{"eki":["265784174"],"zdb":["1466347-8"],"issn":["1879-2294"]},"physDesc":[{"extent":"Online-Ressource"}],"title":[{"title_sort":"Theoretical computer science","title":"Theoretical computer science","subtitle":"the journal of the EATCS"}],"type":{"bibl":"periodical","media":"Online-Ressource"},"note":["Gesehen am 12.04.23"],"disp":"Resource bounded randomness and weakly complete problemsTheoretical computer science","language":["eng"],"recId":"265784174","pubHistory":["1.1975/76 - 412.2011; Vol. 413.2012 -"],"part":{"pages":"195-207","issue":"1","year":"1997","extent":"13","text":"172(1997), 1, Seite 195-207","volume":"172"}}],"physDesc":[{"extent":"13 S."}]} 
SRT |a AMBOSSPIESRESOURCEBO1997 

Similar Items