Thursday, September 11
Milner 317, 1:15 PM
Title: Dedekind zeta functions and the complexity of Hilbert's Nullstellensatz
Abstract: We present a simple, suprisingly fast algorithm for deciding whether a collection of multivariate polynomials with integer coefficients has a complex root. The algorithm is completely different from the usual Groebner basis, homotopy, or resultant techniques, and is instead based on an oracle sampling trick for checking the density of primes p for which the equations have a root mod p. The punchline is that, under a number theoretic assumption, our algorithm is polynomial time if P=NP. Put another way, one gets an alternative approach to proving that P differs from NP: show that Hilbert's Nullstellensatz takes super-polynomial time to solve.
The underlying assumption is a weakening of the Generalized Riemann Hypothesis (GRH) to a statement about the density of zeroes of the underlying Dedekind zeta function. In particular, our hypothesis can hold even if GRH fails. Previously, the results above (via seminal work of Pascal Koiran) were known only under the assumption of the full GRH. Time permitting, we'll also see how the the computation of the dimension of complex algebraic sets, and the detection of rational points on certain algebraic sets, can be sped up as well.