Hard sets are hard to find
Harry Buhrman, Dieter van Melkebeek · 2002
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 complete under /spl les/(n/sup /spl alpha//-tt/sup -/)/sup P/ reductions for NP, the levels of the polynomial-time hierarchy, and PSPACE have p/sub 2/-measure zero for any constant /spl alpha/<1. The /spl les/(n/sup c/-T)/sup P/-complete sets for EXP have p/sub 2/-measure zero for any constant c. Assuming MA/spl ne/EXP, the /spl les//sub tt//sup P/-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/sub 2/-measure zero. Previous to our work, the theorem was only known to hold for /spl les//sub btt//sup p/-reductions. We establish it for /spl les/(n/sup 0/(1)-tt)/sup p/-reductions.