کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10331969 | 686999 | 2005 | 4 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Reviewing bounds on the circuit size of the hardest functions
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
In this paper we review the known bounds for L(n), the circuit size complexity of the hardest Boolean function on n input bits. The best known bounds appear to be 2nn(1+lognnâO(1n))⩽L(n)⩽2nn(1+3lognn+O(1n)). However, the bounds do not seem to be explicitly stated in the literature. We give a simple direct elementary proof of the lower bound valid for the full binary basis, and we give an explicit proof of the upper bound valid for the basis {¬,â§,â¨}.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 95, Issue 2, 31 July 2005, Pages 354-357
Journal: Information Processing Letters - Volume 95, Issue 2, 31 July 2005, Pages 354-357
نویسندگان
Gudmund Skovbjerg Frandsen, Peter Bro Miltersen,