کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4950767 | 1441032 | 2018 | 4 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On the relative power of reduction notions in arithmetic circuit complexity
ترجمه فارسی عنوان
در قدرت نسبی مفاهیم کاهش در پیچیدگی مدار حساب
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We show that the two main reduction notions in arithmetic circuit complexity, p-projections and c-reductions, differ in power. We do so by showing unconditionally that there are polynomials that are VNP-complete under c-reductions but not under p-projections. We also show that the question of which polynomials are VNP-complete under which type of reductions depends on the underlying field.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 130, February 2018, Pages 7-10
Journal: Information Processing Letters - Volume 130, February 2018, Pages 7-10
نویسندگان
Christian Ikenmeyer, Stefan Mengel,