کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
426668 | 686149 | 2009 | 6 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A zero-one law for RP and derandomization of AM if NP is not small
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: A zero-one law for RP and derandomization of AM if NP is not small A zero-one law for RP and derandomization of AM if NP is not small](/preview/png/426668.png)
چکیده انگلیسی
We show that if RP does not have p-measure zero then ZPP = EXP. As corollaries we obtain a zero-one law for RP in EXP, and that both probabilistic classes ZPP and RP have the same measure in EXP. We also prove that if NP does not have p-measure zero then NP = AM.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information and Computation - Volume 207, Issue 7, July 2009, Pages 787-792
Journal: Information and Computation - Volume 207, Issue 7, July 2009, Pages 787-792