COMPUTER SCIENCE COLLOQUIUM

On the complexity of numerical computation

Peter Bro Miltersen DAIMI University of Aarhus

Tuesday, October 10, 2006, at 14:15 Seminar Room

ABSTRACT

We study the problem PosSLP: Given a division-free straight-line program producing an integer N, decide whether N>0. We relate PosSLP to the Blum-Shub-Smale model of computation and we show that PosSLP essentially captures the problem of doing arbitrary-precision numerical computation. We show that the problem of computing the total degree of a multivariate polynomial given by a straight line program reduces to PosSLP. Then, using techniques derived from the construction of uniform constant-depth circuits for integer division by Hesse et al, we show that PosSlp lies in the counting hierarchy, CH. Combining our results with work of Tiwari, we show that the Euclidean Traveling Salesman Problem lies in CH - the previous best upper bound for this important problem (in terms of classical complexity classes) being PSPACE.

Joint work with Eric Allender, Peter Burgisser and Johan Kjeldgaard-Pedersen.

Host: Klaus Meer

---

SDU HOME | IMADA HOME | Previous Page

---

Last modified: Thu Sep 28 13:11:13 CEST 2006

Joan Boyar (joan@imada.sdu.dk)