On Reductions to Sets that Avoid EXPSPACE
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.
Ps-File: On Reductions to Sets that Avoid EXPSPACE