  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 $\neq$ VNP or DSPACE($\log^{\log^{\ast}n} n$)
$\not\subset$ P.
