Abstract
Vikraman Arvind, Johannes Köbler, and Martin Mundhenk
Abstract:
A set B is called EXPSPACE-avoiding, if every subset of B in EXPSPACE
is sparse. Sparse sets and sets of high information density are shown
to be EXPSPACE-avoiding. Investigating the complexity of sets A in EXP
that honestly reduce to EXPSPACE-avoiding sets, we show that if the
reducibility used has a property, called range-constructibility, then
A must also reduce to a sparse set under the same reducibility.