- Authors: H. Buhrman and D. van Melkebeek.
- Reference: Journal of Computer and System Sciences, 59(2): 327-345, 1999.
Special issue for selected papers from the 13th IEEE Conference on
Computational Complexity.
- Earlier version:
Abstract
We investigate the frequency of complete sets for various complexity
classes within EXP under several polynomial-time reductions in the
sense of resource-bounded measure. We show that these sets are scarce:
- The sets that are na-tt-complete for NP, the
levels of the polynomial-time hierarchy, and PSPACE have
p2-measure zero for any constant a < 1.
- The nc-Turing-complete sets for EXP have
p2-measure zero for any constant c.
- Assuming MA <> EXP, the tt-complete sets for EXP
have p-measure zero.
A key ingredient is the Small Span Theorem, which states that for any set
A in EXP at least one of its lower span (i.e., the sets that reduce
to A) or its upper span (i.e., the sets that A reduces to) has
p2-measure zero. Previous to our work,
the best published theorem along these lines held for
reductions with a constant number of queries. We establish it for
tt-reductions that make no(1) queries.
