کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
426419 686058 2015 11 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On fixed-polynomial size circuit lower bounds for uniform polynomials in the sense of Valiant
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
On fixed-polynomial size circuit lower bounds for uniform polynomials in the sense of Valiant
چکیده انگلیسی

We consider the problem of fixed-polynomial lower bounds on the size of arithmetic circuits computing uniform families of polynomials. Assuming the generalised Riemann hypothesis (GRH), we show that for all k  , there exist polynomials with coefficients in MAMA having no arithmetic circuits of size O(nk)O(nk) over CC (allowing any complex constant). We also build a family of polynomials that can be evaluated in AMAM having no arithmetic circuits of size O(nk)O(nk). Then we investigate the link between fixed-polynomial size circuit bounds in the Boolean and arithmetic settings. In characteristic zero, it is proved that NP⊄size(nk)NP⊄size(nk), or MA⊂size(nk)MA⊂size(nk), or NP=MANP=MA imply lower bounds on the circuit size of uniform polynomials in n   variables from the class VNPVNP over CC, assuming GRH. In positive characteristic p  , uniform polynomials in VNPVNP have circuits of fixed-polynomial size if and only if both VP=VNPVP=VNP over FpFp and ModpPModpP has circuits of fixed-polynomial size.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information and Computation - Volume 240, February 2015, Pages 31–41
نویسندگان
, , ,