In this talk, I will survey some results (some dating back more than a
decade) indicating that certain computational complexity classes can be
characterized in terms of efficient reducibility to the (undecidable)
set of Kolmogorov-random strings. There have been a few new
developments, and there are a lot of open questions.
Some of the main results in this line of research:
Let U be a universal Turing machine, and let R_U be {x : K_U(x) is at
least |x|}. That is, R_U is the set of Kolmogorov-random strings, when
K-complexity is defined using universal machine U. When we write "R"
instead of "R_U" in statement, it will mean that the statement holds for
EVERY universal machine U. Let P_tt(A) denote the class of sets that
are polynomial-time non-adaptively reducible to A (also known as the
class of sets that are polynomial-time truth-table reducible to A). Let
P(A) denote the class of sets that are poly-time Turing-reducible to A.
Theorem:...

more