Hard Sets Are Hard to Find

摘要

We investigate the frequency of complete sets for various complexity classes within EXT under several polynomial-time reductions in the sense of resource-bounded measure. We show that these sets are scarce f The sets that are ≤_(n~α-tt)~p -complete for NT, the levels of the polynomial-time hierarchy, and TITALE have p_2-measure zero for any constant α < 1; The ≤_(n~c-Tˉ)~p complete sets for EXT have p_2-measure zero for any constant c; Assuming MA ≠EXT, the ≤_tt~p -complete sets for EXT have p-measure zero. A key ingredient is the Small Span Theorem, which states that for any set A in EXT 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 ≤_btt~p -reductions. We establish it for ≤_(n~o(1)-tt)~p -reductions.