Randomness notions and partial relativization

Abstract. 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. 1