Resource-bounded martingales and computable Dowd-type generic sets.

Martin-Löf defined algorithmic randomness, the use of martingales in this definition and several variants were explored by Schnorr, and Lutz introduced resource-bounded randomness. Ambos-Spies et al. have studied resource-bounded randomness under time-bounds and have shown that resource-bounded randomness implies resource-bounded genericity. While the genericity of Ambos-Spies is based on time-bound on finite-extension strategy, the genericity of Dowd, the main topic of this paper, is based on an analogy of the forcing theorem. For a positive integer r , an oracle D is r -generic in the sense of Dowd ( r -Dowd) if the following holds: If a certain formula F on an exponential-sized portion of D is a tautology then a polynomial-sized subfunction of D forces F to be a tautology. Here, r is the number of occurrences of query symbols in F . The relationship between resource-bounded randomness and Dowd-type genericity has been not clear so far. We show that there exists a primitive recursive function t ( n ) with the following property: Every t ( n ) -random set is r -Dowd for each positive integer r . A proof is done by means of constructing resource-bounded martingales. In our former paper, we left an open problem whether there exists a primitive recursive set which is r -Dowd for every positive integer r . In our recent work, we give an affirmative answer to the problem. The main theorem of the present paper gives an alternative proof of the affirmative answer. [ABSTRACT FROM AUTHOR]