کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
426419 | 686058 | 2015 | 11 صفحه PDF | دانلود رایگان |

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.
Journal: Information and Computation - Volume 240, February 2015, Pages 31–41