On the Complexity of Numerical Analysis

In this talk, we consider two quite different approaches toward
understanding the complexity of fundamental problems in numerical
analysis:

1. The Blum-Shub-Smale model was defined in order to incorporate the real numbers into a computational model, and to provide a framework for classifying the complexity of continuous functions and sets of real numbers. This model gives us the complexity class "polynomial time over the reals', denoted P_R. An important subclass of P_R (denoted P^0_R) arises when machines in this model are provided only with algeraic real numbers.
2. We define a discrete computational problem entirely within the realm of discrete computation (the "generic task of numerical analysis') to focus attention on the computational complexity of the job confronting the designers of numerically stable algorithms.

We show that both of these approaches hinge on the question of understanding the complexity of the following problem, which we call PosSLP:

Given a division-free straight-line program producing an integer N, decide whether N>0.

More precisely, P^PosSLP = the Boolean part of P^0_R, and PosSLP is poly-time equivalent to the "generic task of numerical analysis'.

We show that PosSLP lies in the counting hierarchy. Combining our results with work of Tiwari, we show that the Euclidean Traveling Salesman Problem lies in the counting hierarchy — the previous best upper bound for this important problem (in terms of classical complexity classes) being PSPACE.

A version of the paper is available
http://ftp.cs.rutgers.edu/pub/allender/slp.pdf

This is joint work with Peter Buergisser, Johan Kjeldgaard-Pedersen, and Peter Bro Miltersen.
Eric Allender received his B.A. degree with a double major in Theatre and
Computer Science from the University of Iowa in 1979. After a year traveling
and working abroad, he accepted a President's Fellowship at the Georgia
Institute of Technology, and earned his Ph.D. from Georgia Tech in
1985. He has been at Rutgers since that time, reaching the rank of
full professor in 1997. He has also held visiting positions at
Princeton University, the universities of Wuerzburg and Tuebingen in
Germany, and the Institute of Mathematical Sciences in India.

Prof. Allender is a recognized expert in the field of computational
complexity theory; he has done work on circuit complexity, on Kolmogorov
complexity, and on complexity classes. He has given numerous invited
addresses at computer science symposia worldwide. He succeeded Juris
Hartmanis as the editor of the Computational Complexity Column for the
Bulletin of the European Association for Theoretical Computer Science,
and for three years he chaired the Steering Committee for the annual
IEEE Conference on Computational Complexity. He serves on the Scientific
Board for the Electronic Colloquium on Computational Complexity (ECCC)
and is an editor for the journal Computational Complexity.