کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6874234 | 1441031 | 2018 | 5 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A note on monotone real circuits
ترجمه فارسی عنوان
یک یادداشت در مورد مدارهای یکنواخت واقعی
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We show that if a Boolean function f:{0,1}nâ{0,1} can be computed by a monotone real circuit of size s using k-ary monotone gates then f can be computed by a monotone real circuit of size O(snkâ2) which uses unary or binary monotone gates only. This partially solves an open problem presented in [2]. In fact, in size O(snkâ1), the circuit uses only unary monotone gates and binary addition. We also show that if the monotone Karchmer-Wigderson game of f can be solved by a “real communication protocol” of size s then f can be computed by a monotone real circuit of the same size.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 131, March 2018, Pages 15-19
Journal: Information Processing Letters - Volume 131, March 2018, Pages 15-19
نویسندگان
Pavel HrubeÅ¡, Pavel Pudlák,