Name
Abstract | ||
|---|---|---|
A set B is called EXPSPACE-avoiding, if every subset of B in EXPSPACEis sparse. Sparse sets and sets of high information density (called HIGH setsin [5]) are shown to be EXPSPACE-avoiding. Investigating the complexity ofsets A in EXPSPACE that honestly reduce to EXPSPACE-avoiding sets, weshow that if the reducibility used has a property, called range-constructibility,then A must also reduce to a sparse set under the same reducibility.Keywords: Computational Complexity,... |
Year | DOI | Venue |
|---|---|---|
1995 | 10.1016/0020-0190(95)00138-3 | Inf. Process. Lett. |
Keywords | Field | DocType |
computational complexity,reducibilities | Complexity class,Discrete mathematics,Information density,Combinatorics,Oracle,Reduction (recursion theory),EXPSPACE,Mathematics,Computational complexity theory | Journal |
Volume | Issue | ISSN |
56 | 2 | 0020-0190 |
Citations | PageRank | References |
1 | 0.36 | 10 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Vikraman Arvind | 1 | 296 | 38.18 |
| Johannes Köbler | 2 | 31 | 6.83 |
| M. Mundhenk | 3 | 2 | 0.77 |