کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6874005 | 686415 | 2015 | 28 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A higher-order characterization of probabilistic polynomial time
ترجمه فارسی عنوان
مشخصه مرتبه بالاتر از زمان چند جمله ای احتمالاتی
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
پیچیدگی محاسباتی نامتجانس، کلاسهای احتمالی،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We present RSLR, an implicit higher-order characterization of the class PPâ
of those problems which can be decided in probabilistic polynomial time with error probability smaller than 12. Analogously, a (less implicit) characterization of the class BPPâ
can be obtained. RSLRâ
is an extension of Hofmann's SLRâ
with a probabilistic primitive, which enjoys basic properties such as subject reduction and confluence. Polynomial time soundness of RSLRâ
is obtained by syntactical means, as opposed to the standard literature on SLR-derived systems, which use semantics in an essential way.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information and Computation - Volume 241, April 2015, Pages 114-141
Journal: Information and Computation - Volume 241, April 2015, Pages 114-141
نویسندگان
Ugo Dal Lago, Paolo Parisen Toldin,