Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

I will review a theorem of Pascal Koiran that ought to be better known, in my opinion. Koiran showed that the problem of whether an affine algebraic variety V is non-empty (over Q-bar or C) is in the complexity class Arthur-Merlin, or AM, assuming the Generalized Riemann Hypothesis. AM is closely related to the more famous NP; it is easy to show that the problem is NP-hard . Among other ingredients, the proof uses an effective version of the Hilbert Nullstellensatz due to Brownawell and Kollar, and an effective version of the Cebotarev density theorem that would follow from GRH. The result is also related to the Tarski-Seidenberg theorem on the computability of real points in V, where much less is known about computational complexity.