Complete Sets under Non-Adaptive Reductions are Scarce
Harry Buhrman, Dieter van Melkebeek

Abstract:
We investigate the frequency of complete sets for various complexity classes 
within EXP under non­adaptive reductions in the sense of resource bounded 
measure. We show that these sets are rare:

  * The sets that are complete under <=^p_{n^\alpha-tt}­reductions for NP, the 
    levels of the polynomial­time hierarchy, PSPACE, and EXP have p_2-measure 
    zero for any constant \alpha < 1.
  * Assuming MA \neq EXP, the <=^p_{tt}­complete sets for PSPACE and the
    \Delta­levels of the polynomial­time hierarchy 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 theorem was only known to hold for <=^p_{k-tt}-reductions for 
any constant k. We establish it for <=^p_{n^{o(1)}-tt}-reductions.