کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
426668 686149 2009 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله 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
چکیده انگلیسی

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