Intractability of Hilbert's Nullstellensatz implies algebraic hardness of permanent

Abstract

We study the logical relation of the P-NP separation conjecture in the Blum-Shub-Smale-model over the complex numbers with the P-NP separation conjecture in Valiant's algebraic model. This amounts to comparing Hilbert's Nullstellensatz Problem, that is, deciding feasibility of a given system of polynomial equations over the complex numbers, with the problem of evaluating the permanent of a given complex matrix. We compare the respective uniform models of computations and prove that $P_C\ne N{P}_C$ in the Blum-Shub-Smale-model over $C$ implies the separation $V{P}^0(u)\ne VN{P}^0(u)$ of the uniform versions of Valiant's constant-free complexity classes over $C$. For the nonuniform models we show the analogous implication: the separation $P_C^0(nu)\ne N{P}_C^0(nu)$ of the nonuniform, constant-free Blum-Shub-Smale classes over $C$ implies the separation $V{P}^0\ne VN{P}^0$ of Valiant's constant-free complexity classes over $C$. In the reverse direction, we conjecture that $VN{P}_C⊈{\overline{VP}}_C$ implies that $P_C(nu)\ne N{P}_C(nu)$.

25 pages