Revised: June 16, 2019

Published: December 14, 2019

**Keywords:**algebraic dependence, Jacobian, Arthur-Merlin, approximate polynomial, satisfiability, hitting set, border VP, finite field, PSPACE, EXPSPACE, GCT Chasm

**Categories:**complexity theory, algebraic complexity, algebraic dependence, Jacobian, Arthur-Merlin, polynomials, approximate polynomial, satisfiability, hitting set, finite field, PSPACE, EXPSPACE, GCT Chasm, CCC, CCC 2018 special issue

**ACM Classification:**I.1, F.2.1, F.1.3, G.1.2

**AMS Classification:**03D15, 14Q20

**Abstract:**
[Plain Text Version]

Testing whether a set $\mathbf{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^{\#\Pclass}$
(Mittmann, Saxena, Scheiblechner, Trans. AMS 2014).
In this article we put the problem in $\AMcapcoAM$.
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 $\mathbf{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
$\mathbf{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
$\mathbf{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 $\VPbar$
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).