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,

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.