Limitations of Efficient Reducibility to the Kolmogorov Random Strings
John M. Hitchcock · Computability · 2012
We show the following results for polynomial-time reducibility to RC, the set of Kolmogorov random strings.1.If P = NP, then SAT does not dtt-reduce to RC. 2. If PH does not collapse, then SAT does not n α --reduce to RC for any α < 1. 3. If PH does not collapse, then SAT does not n α -T-reduce to RC for any α < 1 2 .4. There is a problem in E that does not dtt-reduce to RC. 5.There is a problem in E that does not n α --reduce to RC, for any α < 1. 6.There is a problem in E that does not n α -T-reduce to RC, 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.