Resource bounded randomness and weakly complete problems
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...
Saved in:
| Main Authors: | , , |
|---|---|
| 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 
|
| Author Notes: | Klaus Ambos-Spies, Sebastiaan A. Terwijn, Zheng Xizhong |
Search Result 1
