On the Complexity of Numerical Analysis

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperJournal articleResearch

  • Eric Allender, Denmark
  • Peter Bürgisser, Denmark
  • Johan Kjeldgaard-Pedersen, Denmark
  • Peter Bro Miltersen
  • Department of Computer Science
We study two quite different approaches to understanding the complexity of fundamental problems in numerical analysis. We show that both 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. We show that PosSLP lies in the counting hierarchy, and we show that if A is any language in the Boolean part of Polynomial-time over the Reals accepted by a machine whose machine constants are algebraic real numbers, then A is in P^PosSLP. 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.
Original languageEnglish
JournalElectronic Colloquium on Computational Complexity
IssueTR05-037
Pages (from-to)1-12
ISSN1433-8092
Publication statusPublished - 2005

See relations at Aarhus University Citationformats

ID: 689278