Characterizing the strongly jump-traceable sets via randomness (Q456804): Difference between revisions

Strong jump-traceability was introduced for some very technical reasons. Though the class was known to be a proper subset of \(K\)-trivial sets, it was not clear whether there is a connection between the class and randomness. The authors in the paper under review reveal a significant connection between these notions. They show that c.e. strongly jump-traceable sets are precisely those c.e. sets computable from every superlow random set. Moreover, they are also precisely those c.e. sets computable from every superhigh random set.