Where does randomness help when deciding algebraic geometry over $\mathbb{C}$?

Question

If we have a single straight line program expressing a multivariate polynomial equation with integer coefficients, the Schwartz-Zippel lemma gives a simple randomized algorithm for deciding whether the equation is always true. We can similarly decide if a single polynomial inequation is always true over $\mathbb{C}$, since $p(z_1,\ldots,z_n) \ne 0$ for all $z_i$ iff the polynomial is a nonzero constant.

Does the simplicity of randomized checking extend to any systems of multivariate polynomial equations? In particular, is there a simple algorithm for deciding whether $$p(z_1,\ldots,z_n) = 0 \implies q(z_1,\dots,z_n) = 0$$ where $p,q$ are straight line programs over $\mathbb{C}$ with integer coefficients? I'm fairly sure randomness does not provide simple algorithms if we go to arbitrary systems of equations and inequations, but I'm curious where the boundary is between easy and hard.

Answer 1

• For the question of when does $p=0 \Rightarrow q=0$, randomness can indeed help, as follows. First, factor $p$ (uses randomness when $p$ is given as a straight-line program; doesn't need randomness if $p$ is given as a coefficient vector). Let $\tilde{p}$ denote the square-free version of $p$ - that is, if $p=p_1^{k_1} p_2^{k_2} \dotsb p_\ell^{k_\ell}$ then $\tilde{p} = p_1 p_2 \dotsb p_\ell$. Then $q=0$ follows from $p=0$ iff $\tilde{p}$ divides $q$, which happens iff $q$ is of the form $q=p_1^{k'_1} \dotsb p_\ell^{k'_\ell} f$ with all of the $k'_j$ strictly positive. The latter can be checked by factoring $q$ (uses randomness, as before).

• For the general question of $p_1=\dotsb=p_k=0 \Rightarrow q=0$, randomness seems not to help from the complexity perspective, as this problem is $\mathsf{EXPSPACE}$-complete (randomness may help in practice though...).

• For the problem of telling whether the variety $\{\vec{x} : p_1(x)=\dotsb=p_k(x)=0\}$ is empty or not (for polynomials given by a list of monomials and coefficients - which is "sparse but not succinct", that is, not SLPs), randomness also seems to help: assuming GRH, this problem is in $\mathsf{RP}^{\mathsf{NP}}$ by a result of Koiran. It is $\mathsf{NP}$-hard, and not known to be in $\mathsf{P}^{\mathsf{NP}}$.