On Annihilators of Explicit Polynomial Maps

09/14/2023
by   Prerona Chatterjee, et al.
0

We study the algebraic complexity of annihilators of polynomials maps. In particular, when a polynomial map is `encoded by' a small algebraic circuit, we show that the coefficients of an annihilator of the map can be computed in PSPACE. Even when the underlying field is that of reals or complex numbers, an analogous statement is true. We achieve this by using the class VPSPACE that coincides with computability of coefficients in PSPACE, over integers. As a consequence, we derive the following two conditional results. First, we show that a VP-explicit hitting set generator for all of VP would separate either VP from VNP, or non-uniform P from PSPACE. Second, in relation to algebraic natural proofs, we show that proving an algebraic natural proofs barrier would imply either VP ≠ VNP or DSPACE(log^log^∗n n) ⊄ P.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset