Complexity and Real Computation

Lenore Blum & Stephen Smale

TUTORIAL

The tutorial will to a great extent be based on the material in the book of the same title written jointly by L. Blum, F. Cucker, M. Shub and S. Smale, and published by Springer 1998. Thus, NP-completeness over a general field will be important. With the field of 2 elements this is the work of Cook-Karp. With the field of real numbers one comes close to the algorithms of Newton and Gauss and eventually modern numerical analysis. With the field of complex numbers one obtains a uniform version of classical algebaic complexity theory.

A natural extension of the problem “is P = NP ?” to the complex numbers is developed. Now the universal problem is Hilbert’s Nullstellensatz considered as a decision problem. Relations of the extended problem to the original Cook-Karp problem will be discussed.

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