کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
426082 685991 2013 13 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Permanent does not have succinct polynomial size arithmetic circuits of constant depth
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Permanent does not have succinct polynomial size arithmetic circuits of constant depth
چکیده انگلیسی

We show that over fields of characteristic zero there does not exist a polynomial p(n)p(n) and a constant-free succinct   arithmetic circuit family {Φn}{Φn} using division by constants,3 where ΦnΦn has size at most p(n)p(n) and depth O(1)O(1), such that ΦnΦn computes the n×nn×n permanent. A circuit family {Φn}{Φn} is succinct if there exists a nonuniform   Boolean circuit family {Cn}{Cn} with O(logn) many inputs and size no(1)no(1) such that CnCn can correctly answer direct connection language queries about ΦnΦn – succinctness is a relaxation of uniformity.To obtain this result we develop a novel technique that further strengthens the connection between black-box derandomization of polynomial identity testing and lower bounds for arithmetic circuits. From this, we obtain the lower bound by giving an explicit construction, computable in the polynomial hierarchy, of a hitting set for arithmetic circuits.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information and Computation - Volume 222, January 2013, Pages 195–207
نویسندگان
, ,