کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
9657718 | 690091 | 2005 | 4 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A note on the circuit complexity of PP
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
In this short note, we show that for any integer k, there are languages in the complexity class PP that do not have Boolean circuits of size nk.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 347, Issues 1â2, 30 November 2005, Pages 415-418
Journal: Theoretical Computer Science - Volume 347, Issues 1â2, 30 November 2005, Pages 415-418
نویسندگان
N.V. Vinodchandran,