Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
436649 | Theoretical Computer Science | 2007 | 10 Pages |
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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Ryan C. Harkins, John M. Hitchcock,