کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
427667 | 686535 | 2012 | 7 صفحه PDF | دانلود رایگان |
We make progress towards proving an equivalence between the problem of derandomization of arithmetic circuit identity testing (ACIT), and the arithmetic circuit complexity of the permanent defined by pern=∑σ∈Sn∏i=1nxiσ(i). We develop an ACIT-based derandomization hypothesis, and show this is a necessary condition for proving that permanent has super-polynomial arithmetic circuits over fields of characteristic zero. Informally, this hypothesis poses the existence of a subexponential size hitting set computable by subexponential size uniform TC0TC0 circuits against size n arithmetic circuits with multilinear output. Assuming the Generalized Riemann Hypothesis (GRH), we show that this hypothesis is sufficient for proving that either permanent does not have polynomial size (nonuniform) arithmetic circuits, or that the Boolean circuit class uniform TC0TC0 is strictly contained in uniform NC2NC2.
► We investigate arithmetic circuit identity testing and the complexity of the permanent.
► We give a necessary condition for proving that permanent has super-polynomial arithmetic circuit size.
► We show that this condition implies the disjunction of an arithmetic and boolean lower bound.
Journal: Information Processing Letters - Volume 112, Issue 24, 31 December 2012, Pages 969–975