On languages with very high information content
Ronald V. Book, Jack H. Lutz · 2003
It is shown that any language in ESPACE that is bounded truth-table reducible in polynomial time to a set with very high space-bounded Kolmogorov complexity must be bounded truth-table reducible in polynomial time to a sparse set.>