**News**

22 Sep 2014. Accepted to publish in TOCS

24 Mar 2014. Submitted

**Title**

Reducibilities relating to Schnorr randomness

**Type**

Full paper

**Journal**

Theory of Computing Systems, 58(3), 441-462, 2016.

DOI: 10.1007/s00224-014-9583-3

**Abstract**

Some measures of randomness have been introduced for Martin- L ̈of randomness such as K-reducibility, C-reducibility and vL-reducibility. In this paper we study Schnorr-randomness versions of these reducibilities. In particular, we characterize the computably-traceable reducibility via relative Schnorr randomness, which was asked in Nies’ book (Problem 8.4.22). We also show that Schnorr reducibility implies uniform-Schnorr-randomness version of vL-reducibility, which is the Schnorr-randomness version of the result that K-reducibility implies vL-reducibility.

**Download**

preprint