- 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:
- Hard Sets Are Hard to Find.
In
*Proceedings of the 13th IEEE Conference on Computational Complexity*, pages 170-181, 1998.

- Hard Sets Are Hard to Find.
In

- The sets that are
*n*-tt-complete for NP, the levels of the polynomial-time hierarchy, and PSPACE have p^{a}_{2}-measure zero for any constant*a*< 1. - The
*n*-Turing-complete sets for EXP have p^{c}_{2}-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
p_{2}-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 *n ^{o(1)}* queries.

dieter@cs.wisc.edu