Humboldt-Universität zu Berlin - Mathematisch-Naturwissenschaftliche Fakultät - Komplexität und Kryptografie

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