A set $B$ is called {\it EXPSPACE-avoiding}, if every subset of $B$ in EXPSPACE is sparse. For example, sets of high information density (called $\high$ sets in [R.Book and J.Lutz: On languages with very high space-bounded Kolmogorov complexity. SIAM Journal on Computing 22(2) (1993) 395-402.] are shown to be EXPSPACE-avoiding. Investigating the complexity of sets $A$ in ESPACE that honestly reduce to EXPSPACE-avoiding sets, we show that if the reducibility used has a property, called {\it range-constructibility}, then $A$ must also reduce to a sparse set under the same reducibility.
Back to my homepage