Randomness notions and partial relativization

We study the computational complexity of an oracle set using a number of notions of randomness that lie between Martin-Löf randomness and 2-randomness in terms of strength. These notions are weak 2-randomness, weak randomness relative to ∅′, Demuth randomness and Schnorr randomness relative to ∅′. W...

Full description

Saved in:
Bibliographic Details
Published in:Israel journal of mathematics 2012-10, Vol.191 (2), p.791-816
Main Authors: Barmpalias, George, Miller, Joseph S., Nies, André
Format: Article
Language:English
Subjects:
Algebra
Analysis
Applications of Mathematics
Group Theory and Generalizations
Mathematical and Computational Physics
Mathematics
Mathematics and Statistics
Theoretical
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We study the computational complexity of an oracle set using a number of notions of randomness that lie between Martin-Löf randomness and 2-randomness in terms of strength. These notions are weak 2-randomness, weak randomness relative to ∅′, Demuth randomness and Schnorr randomness relative to ∅′. We characterize the oracles A such that ML[ A ] ⊆ C , where C is such a randomness notion and ML[ A ] denotes the Martin-Löf random reals relative to A , using a new meta-concept called partial relativization. We study the reducibility associated with weak 2-randomness and relate it with LR -reducibility.
ISSN:0021-2172
1565-8511
DOI:10.1007/s11856-012-0012-5