In this talk, I consider the question of whether or not there is an efficient reduction
from the halting problem to the set of Kolmogorov-random strings.  It is known that
there is an efficient nonuniform reduction (that is, a reduction computed by polynomial-size
circuits) but the only "efficient" uniform reduction known is the (disjunctive) truth-table that was presented by Kummer -- and the running time for that reduction is known to depend on the choice of the universal Turing machine that is used to define Kolmogorov complexity.  For disjunctive reductions, it is known that exponential time at least is required.  Motivation for this question comes from complexity theory.  Derandomization techniques allow us to show that
PSPACE is poly-time Turing reducible to the K-random strings, and NEXP is NP-reducible
to this same set.  No "efficient" uniform reductions to the K-random strings are known for any larger complexity class.