We investigate the consequences of the existence of ``efficiently describable'' hitting sets for polynomial sized algebraic circuit ($\mathsf{VP}$), in particular, \emph{$\mathsf{VP}$-succinct hitting sets}.
Existence of such hitting sets is known to be equivalent to a ``natural-proofs-barrier'' towards algebraic circuit lower bounds, from the works that introduced this concept (Forbes \etal (2018), Grochow \etal (2017)).
We show that the existence of $\mathsf{VP}$-succinct hitting sets for $\mathsf{VP}$ would either imply that $\mathsf{VP} \neq \mathsf{VNP}$, or yield a fairly strong lower bound against $\mathsf{TC}^0$ circuits, assuming the Generalized Riemann Hypothesis (GRH).
This result is a consequence of showing that designing efficiently describable ($\mathsf{VP}$-explicit) hitting set generators for a class
$\mathcal{C}$, is essentially the same as proving a separation between $\mathcal{C}$ and $\mathsf{VPSPACE}$: the algebraic analogue of
\textsf{PSPACE}. More formally, we prove an upper bound on \emph{equations} for polynomial sized algebraic circuits ($\mathsf{VP}$), in terms of
$\mathsf{VPSPACE}$.
Using the same upper bound, we also show that even \emph{sub-polynomially explicit hitting sets} for $\mathsf{VP}$ --- much weaker than $\mathsf{VP}$-succinct hitting sets that are almost polylog-explicit --- would imply that either $\mathsf{VP} \neq \mathsf{VNP}$ or that $\mathsf{P} \neq \mathsf{PSPACE}$. This motivates us to define the concept of \emph{cryptographic hitting sets}, which we believe is interesting on its own.
Improved the consequences of the previous statement.
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.