#### Theory Seminar

# 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:

- 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.
- 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.