Geometric Complexity Theory V: Equivalence between Blackbox Derandomization of Polynomial Identity Testing and Derandomization of Noether's Normalization Lemma

摘要

It is shown that black-box derandomization of polynomial identity testing (PIT) is essentially equivalent to derandomization of Noether's Normalization Lemma for explicit algebraic varieties, the problem that lies at the heart of the foundational classification problem of algebraic geometry. Specifically: (1) It is shown that in characteristic zero black-box derandomization of PIT for diagonal depth three circuits brings the problem of derandomizing Noether's Normalization Lemma, for the ring of invariants of any explicit linear action of a classical algebraic group of constant dimension, from EXPSPACE (where it is currently) to P. Next it is shown that assuming the Generalized Riemann Hypothesis (GRH), instead of the black-box derandomization hypothesis, brings the problem from EXPSPACE to quasi-PH, instead of P. Thus black-box derandomization of diagonal depth three circuits takes us farther than GRH here on the basis of the current knowledge. Variants of the main implication are also shown assuming, instead of the black-box derandomization hypothesis in characteristic zero, Boolean lower bounds for constant-depth threshold circuits or uniform Boolean conjectures, in conjunction with GRH. These results may explain in a unified way why proving lower bounds or derandomization results for constant-depth arithmetic circuits in characteristic zero or constant-depth Boolean threshold circuits, or proving uniform Boolean conjectures without relativizable proofs has turned out to be so hard, and also why GRH has turned out to be so hard from the complexity-theoretic perspective. Thus this investigation reveals that the foundational problems of Geometry (classification and GRH) and Complexity Theory (lower bounds and derandomization) share a common root difficulty that lies at the junction of these two fields. We refer to it as the GCT chasm. (2) It is shown that black-box derandomization of PIT in a strengthened form implies derandomization of Noether's Normalization - emma in a strict form for any explicit algebraic variety. (3) Conversely, it is shown that derandomization of Noether's Normalization Lemma in a strict form for specific explicit varieties implies this strengthened form of black box derandomization of PIT and its various variants. (4) A unified geometric complexity theory (GCT) approach to derandomization and classification is formulated on the basis of this equivalence.