On Languages with Very High Space-Bounded Kolmogorov Complexity
Ronald V. Book, Jack H. Lutz · SIAM Journal on Computing · 1993
It is shown that if a language recognizable in exponential space is bounded truth-table reducible in polynomial time to a language with very high space-bounded Kolmogorov complexity, then it is bounded truth-table reducible in polynomial time to a sparse language. There are a number of corollaries, including the following: (a) no language with very high space-bounded Kolmogorov complexity is $ \leqslant _{btt}^{\text{P}} $-hard for NP, unless ${\text{P}} = {\text{NP}}$; (b) no language with very high space-bounded Kolmogorov complexity is $ \leqslant _{btt}^{\text{P}} $-hard for the class of languages accepted in exponential time.