Limitations of Efficient Reducibility to the Kolmogorov Random Strings

Abstract:
We show the following results for polynomial-time reducibility to R_C, the set of Kolmogorov random strings.

If P ≠ NP, then SAT does not dtt-reduce to R_C.
If PH does not collapse, then SAT does not n^α-tt-reduce to R_C for any α < 1.
If PH does not collapse, then SAT does not n^α-T-reduce to R_C for any α < 1/2.
There is a problem in E that does not dtt-reduce to R_C.
There is a problem in E that does not n^α-tt-reduce to R_C for any α < 1.
There is a problem in E that does not n^α-T-reduce to R_C for any α < 1/2.

These results hold for both the plain and prefix-free variants of Kolmogorov complexity and are also independent of the choice of the universal machine.

Computability 1(1):39-43, 2012.
[DOI | PDF]
Lower Bounds for Reducibility to the Kolmogorov Random Strings, Proceedings of the 6th Conference on Computability in Europe (Ponta Delgada, Azores, Portugal, June 30-July 4, 2010), Lecture Notes in Computer Science 6158, pages 195--200. Springer-Verlag, 2010.
[DOI]