loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
21st Annual IEEE Conference on Computational Complexity (CCC'06)
On the Complexity of Numerical Analysis
Prague, Czech Republic
July 16-July 20
ISBN: 0-7695-2596-2
Eric Allender, Rutgers, the State University of NJ, USA
Peter Burgisser, Paderborn University, Germany
Johan Kjeldgaard-Pedersen, Decision Sciences Practice, Denmark
Peter Bro Miltersen, University of Aarhus, Denmark
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 gt 0. We show that PosSLP lies in the counting hierarchy, and 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.
Citation:
Eric Allender, Peter Burgisser, Johan Kjeldgaard-Pedersen, Peter Bro Miltersen, "On the Complexity of Numerical Analysis," ccc, pp.331-339, 21st Annual IEEE Conference on Computational Complexity (CCC'06), 2006
Usage of this product signifies your acceptance of the Terms of Use.