Lower Bounds for Reducibility to the Kolmogorov Random Strings

摘要

We show the following results for polynomial-time reducibility to Re, 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 nQ-tt-reduce to Re for any a < 1. 3. If PH does not collapse, then SAT does not n^-T-reduce to Re for any a < 1. 4. There is a problem in E that does not dtt-reduce to Re- 5. There is a problem in E that does not nQ-tt-reduce to Re, for any a< 1. 6. There is a problem in E that does not na-T-reduce to Re, 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.