ICM 1998, Berlin, Aug. 18–27

Abstracts of Short Communications and Posters

Section:

14. Mathematical Aspects of Computer Science

1991 MS Classification: 14, 51, 68 Mbakop, Guy Merlin, Institut für Mathematik, Humboldt-Universität zu Berlin An Efficient Algorithm for Solving Real Polynomial Equations: The Complete Intersection Case The talk concerns the algorithmic problem of finding at least one representative point in each connected component of a real compact smooth variety defined by a regular sequence of multivariate polynomials with rational coefficients. The algorithm represented by an arithmetic network consists in transferring to the real case a procedure that finds the complex zeros of a given zero-dimensional polynomial equation system in non-uniformal time that is polynomial in the length of the input (given by an arithmetic circuit) and an adequately defined geometric degree of the equation system. Reference: B. Bank, M. Guisti, J. Heintz, G. M. Mbakop, Polar Varieties, Real Equation Solving, and Data Structures: The Hypersurface case. Journal of Complexity 13, 5 − 27 (1997)