کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4950767 1441032 2018 4 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On the relative power of reduction notions in arithmetic circuit complexity
ترجمه فارسی عنوان
در قدرت نسبی مفاهیم کاهش در پیچیدگی مدار حساب
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
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
نویسندگان
, ,