Calculabilité réelle et complexe

Lenore Blum & Stephen Smale

COURS INTENSIF

Ce cours intensif sera basé, pour l’essentiel, sur le texte du même titre de L. Blum, F. Cucker, M. Shub et S. Smale, publié par Spriger en 1998. La notion de problème NP-complet (NP-complétude) sur un corps arbitraire aura un rôle central. Pour le corps à deux éléments cette notion est due à Cook-Karp. Sur le corps des nombres réels elle s’approche des algorithmes de Newton et Gauss et, donc, de l’analyse numérique moderne. Pour le corps des nombres complexes, on obtient une version uniforme de la théorie classique de la complexité algébrique.

Nous allons développer une extension naturelle du problème “P = NP” aux nombres complexes. Dans ce cas, le problème universel est le théorème des zéros de Hilbert considéré comme un problème de décision. Nous discuterons les relations de ce problème étendu avec le problème originel de Cook-Karp.

Addresses Lenore Blum : Computer Science Department, Carnegie Mellon University, Pittsburgh, PA 15213, USA

E-mail: lblum@icsi.berkeley.edu

Stephen Smale: Mathematics Department, City University of Hong Kong, Tat Chee Ave., Kowloon, Hong Kong, People’s Republic of China

E-mail: masmale@Math.cityu.edu.hk