Algebraic Dependencies And Pspace Algorithms In Approximative Complexity Over Any Field

Abstract

Testing whether a set f of polynomials has an algebraic dependence is a basic problem with several applications. The polynomials are given as algebraic circuits. The complexity of algebraic independence testing is wide open over finite fields (Dvir, Gabizon, Wigderson, FOCS'07). Previously, the best complexity bound known was NP#P (Mittmann, Saxena, Scheiblechner, Trans. AMS 2014). In this article we put the problem in AM∩coAM. In particular, dependence testing is unlikely to be NP-hard. Our proof uses methods of algebraic geometry. We estimate the size of the image and the sizes of the preimages of the polynomial map f over the finite field. A gap between the corresponding sizes for independent and for dependent sets of polynomials is utilized in the AM protocols. Next, we study the open question of testing whether every annihilator of f has zero constant term (Kayal, CCC'09). We introduce a new problem called approximate polynomial satisfiability (APS), which is equivalent to the preceding question by a classical characterization in terms of the Zariski closure of the image of f. We show that APS is NP-hard and, using ideas from algebraic geometry, we put APS in PSPACE. (The best previous bound was EXPSPACE via Gröbner basis computation.) As an unexpected application of this to approximative complexity theory we obtain that, over any field, hitting sets for VP¯¯¯¯¯¯¯ can be constructed in PSPACE. This solves an open problem posed in (Mulmuley, FOCS'12, J. AMS 2017), greatly mitigating the GCT Chasm (exponentially in terms of space complexity).