ON REDUCTIONS TO SETS THAT AVOID EXPSPACE

Authors
ARVIND V KOBLER J MUNDHENK M
Citation
V. Arvind et al., ON REDUCTIONS TO SETS THAT AVOID EXPSPACE, Information processing letters, 56(2), 1995, pp. 109-114
Citations number
12
Categorie Soggetti
Information Science & Library Science","Computer Science Information Systems
Journal title
Information processing letters → ACNP
ISSN journal
00200190
Volume
56
Issue
2
Year of publication
1995
Pages
109 - 114
Database
ISI
SICI code
0020-0190(1995)56:2<109:ORTSTA>2.0.ZU;2-6
Abstract
A set B is called EXPSPACE-avoiding, if every subset of B in EXPSPACE is sparse. For example, sets of high information density (called HIGH sets in [5]) are shown to be EXPSPACE-avoiding. Investigating the comp lexity of sets A in EXPSPACE that honestly reduce to EXPSPACE-avoiding sets, we show that if the reducibility used has a property, called ra nge-constructibility, then A must also reduce to a sparse set under th e same reducibility.