کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6872459 | 681651 | 2014 | 10 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Hardness of learning loops, monoids, and semirings
ترجمه فارسی عنوان
سختی حلقه های یادگیری، مونوئید و نیمه نقره
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We show that each randomized o(|G|2)-query algorithm can recover only an expected o(1) fraction of the Cayley table of some finite Abelian loop (G,â
), where both multiplication and inversion queries are allowed. Furthermore, each randomized o(|R|2)-query algorithm can recover only an expected o(1) fraction of any of the Cayley tables of some finite commutative semiring (R,+,â
), with (R,+) being a commutative aperiodic monoid, where each query may ask for x+y or xâ
y for any x, yâR.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 162, 10 January 2014, Pages 149-158
Journal: Discrete Applied Mathematics - Volume 162, 10 January 2014, Pages 149-158
نویسندگان
Ching-Lueh Chang,