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.

1. If P ≠ NP, then SAT does not dtt-reduce to R_C.

2. If PH does not collapse, then SAT does not n^α--reduce to R_C for any α < 1.

3. If PH does not collapse, then SAT does not n^α-T-reduce to R_C for any α < ½.

4. There is a problem in E that does not dtt-reduce to R_C.

5. There is a problem in E that does not n^α--reduce to R_C, for any α < 1.

6. There is a problem in E that does not n^α-T-reduce to R_C, for any α < ½.

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.