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.