期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2002
卷号：2002
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：We show that derandomizing Polynomial Identity Testing is, essentially, equivalent to proving circuit lower bounds for NEXP. More precisely, we prove that if one can test in polynomial time (or, even, nondeterministic subexponential time, infinitely often) whether a given arithmetic circuit over integers computes an identically zero polynomial, then either (i) NEXP\not\subset P/poly or (ii) Permanent is not computable by polynomial-size arithmetic circuits. We also prove a (partial) converse: If Permanent requires superpolynomial-size arithmetic circuits, then one can test in subexponential time whether a given arithmetic formula computes an identically zero polynomial. Since Polynomial Identity Testing is a coRP problem, we obtain the following corollary: If RP=P (or, even, coRP\subseteq\cap_{\epsilon>0} NTIME(2^{n^{\epsilon}}), infinitely often), then NEXP is not computable by polynomial-size arithmetic circuits. Thus, establishing that RP=coRP or BPP=P would require proving superpolynomial lower bounds for Boolean or arithmetic circuits. Our techniques allow us to prove an unconditional circuit lower bound for a language in NEXP^{RP}: we prove that either (i) Permanent is not computable by polynomial-size arithmetic circuits, or (ii) NEXP^{RP}\not\subset P/poly. Finally, we prove that NEXP\not\subset P/poly if both BPP=P and the low-degree testing is in P; here, the low-degree testing is the problem of checking whether a given Boolean circuit computes a function that is close to some low-degree polynomial over a finite field.
