Characterizing the strongly jump-traceable sets via randomness

We show that if a set AA is computable from every superlow 11-random set, then AA is strongly jump-traceable. Together with a result of Greenberg and Nies [Noam Greenberg, André Nies, Benign cost functions and lowness properties, J. Symbolic Logic 76 (1) (2011) 289–312], this theorem shows that the computably enumerable (c.e.) strongly jump-traceable sets are exactly the c.e. sets computable from every superlow 11-random set.We also prove the analogous result for superhighness: a c.e. set is strongly jump-traceable if and only if it is computable from every superhigh 11-random set.Finally, we show that for each cost function cc with the limit condition there is a 11-random Δ20 set YY such that every c.e. set A⩽TY obeys cc. To do so, we connect cost function strength and the strength of randomness notions. Together with a theorem of Greenberg and Nies (ibd.), this result gives a full correspondence between obedience of cost functions and being computable from Δ201-random sets.