Upward Separations and Weaker Hypotheses in Resource-Bounded Measure

Ryan C. Harkins and John M. Hitchcock

Abstract: We consider resource-bounded measure in double-exponential-time complexity classes. In contrast to complexity class separation translating downwards, we show that measure separation translates upwards. For example,

μp(NP) ≠ 0 ⇒ μe(NE) ≠ 0 ⇒ μexp(NEXP) ≠ 0.

We also show that if NE does not have e-measure 0, then the NP-machine hypothesis holds. We give oracles relative to which the converses of these statements do not hold. Therefore the hypothesis on the e-measure of NE is relativizably weaker than the often-investigated p-measure hypothesis on NP, but it has many of the same consequences.