Hard Sets Are Hard to Find

摘要

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 ⩽pnα−tt-complete for NP, the levels of the polynomial-time hierarchy, and PSPACE have p2-measure zero for any constant α<1; The ⩽pnc−T-complete sets for EXP have p2-measure zero for any constant c; Assuming MA≠EXP, the ⩽ptt-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 ⩽pbtt-reductions. We establish it for ⩽pno(1)-tt-reductions.