On the Complexity of Numerical Analysis
Authors:
- Eric AllenderEAEric Allender
- Peter BürgisserPBPeter Bürgisser
- Johan Kjeldgaard-PedersenJKJohan Kjeldgaard-Pedersen
- Peter Bro MiltersenPMPeter Bro Miltersen
- 1 January 2009
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 38 (5) , 1987-2006
Abstract
We study two quite different approaches to understanding the complexity of fundamental problems in numerical analysis: (a) the Blum–Shub–Smale model of computation over the reals; and (b) a problem we call the “generic task of numerical computation,” which captures an aspect of doing numerical computation in floating point, similar to the “long exponent model” that has been studied in the numerical computing community. 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$. In the Blum–Shub–Smale model, polynomial-time computation over the reals (on discrete inputs) is polynomial-time equivalent to PosSLP when there are only algebraic constants. We conjecture that using transcendental constants provides no additional power, beyond nonuniform reductions to PosSLP, and we present some preliminary results supporting this conjecture. The generic task of numerical computation is also polynomial-time equivalent to PosSLP. We prove that PosSLP lies in the counting hierarchy. Combining this with work of Tiwari, we obtain 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. In the course of developing the context for our results on arithmetic circuits, we present some new observations on the complexity of the arithmetic circuit identity testing (ACIT) problem. In particular, we show that if $n!$ is not ultimately easy, then ACIT has subexponential complexity.
Keywords
This publication has 54 references indexed in Scilit:
- PRIMES is in PAnnals of Mathematics, 2004
- Primality and identity testing via Chinese remainderingJournal of the ACM, 2003
- On TC0, AC0, and Arithmetic CircuitsJournal of Computer and System Sciences, 2000
- On the intractability of Hilbert’s Nullstellensatz and an algebraic version of “NP≠P?”Duke Mathematical Journal, 1995
- Computing over the reals with addition and orderTheoretical Computer Science, 1994
- Bits and relative order from residues, space efficientlyInformation Processing Letters, 1994
- Complexity classes defined by counting quantifiersJournal of the ACM, 1991
- Probabilistic Algorithms for Deciding Equivalence of Straight-Line ProgramsJournal of the ACM, 1983
- A probabilistic remark on algebraic program testingInformation Processing Letters, 1978
- All Algebraic Functions Can Be Computed FastJournal of the ACM, 1978