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...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Chapter/Article |
| Language: | English |
| Published: |
1994
|
| In: |
Algorithms and computation
Year: 1994, Pages: 369-377 |
| DOI: | 10.1007/3-540-58325-4_201 |
| Online Access: | Verlag: https://dx.doi.org/10.1007/3-540-58325-4_201
|
| Author Notes: | Klaus Ambos-Spies, Sebastiaan A. Terwijn, Zheng Xizhong |
Search Result 1