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

چکیده انگلیسی
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
Journal: Theoretical Computer Science - Volume 389, Issues 1–2, 10 December 2007, Pages 162–171
نویسندگان
Ryan C. Harkins, John M. Hitchcock,