Maurice Rojas, Texas A & M
On the Effectivity of Number Theory in Polynomial System Solving
One of the most basic notions in polynomial system solving
is feasibility: does your system of equations have any roots? We will
explore the algorithmic complexity of this problem, focussing on
sparse polynomial systems over the real numbers and complex numbers.
Over the real numbers, we will determine the threshold between
polynomial-time and NP-hardness, as a function of the number of monomial
terms. In particular, we will give polynomial-time algorithms where only
exponential-time algorithms were known before, and we will see how Diophantine
approximation enters in an unexpected way.
Over the complex numbers, we will see algorithms completely
different from homotopy, resultants, and Grobner bases; and how the
Generalized Riemann Hypothesis enters our setting. In particular, we
show how earlier number-theoretic algorithms (of Grigoriev, Karpinski,
Odlyzo, and Koiran), depending on unproven number-theoretic hypotheses,
can be made unconditional.
No background in number theory, complexity theory, or
algebraic geometry is assumed.