کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
436649 690021 2007 10 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Upward separations and weaker hypotheses in resource-bounded measure
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Upward separations and weaker hypotheses in resource-bounded measure
چکیده انگلیسی

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 389, Issues 1–2, 10 December 2007, Pages 162–171
نویسندگان
, ,