Marie-Françoise Roy, IRMAR (CNRS UMR 6625 and Rennes University) and FRISCO Project

``Algorithms for real algebraic geometry: recent results and open problems''

April 9, 1998

The decidabiity of real algebra was proved by Tarski and Seidenberg, whose original ideas still play an important role in the development of algorithms in real algebraic geometry.

After quickly sketching the history of the topic and the main ideas involved, we shall discuss recent results on the complexity of Tarski-Seidenberg principle and on other more geometric problems that are related to connectedness.

We shall discuss an important open problem; the complexity of the real nullstellensatz and positivstellensatz. This problem is much less well understood than is the complexity of the nullstellensatz in the algebraically closed case. The first effectivity result for the real nullstellensatz (due to H. Lombardi) only appeared in 1991 while the effectivity of the nullstellensatz in the algebraically closed case was already known (due to G. Hermann) in Hilbert's time.