On the complexity of numerical analysis

E Allender; J Kjeldgaard-Pedersen; P Burgisser; P Miltersen

doi:10.1109/CCC.2006.30

Back

Conference proceeding

On the complexity of numerical analysis

E Allender, J Kjeldgaard-Pedersen, P Burgisser and P Miltersen

21st Annual IEEE Conference on Computational Complexity (CCC'06), Vol.2006, pp.9 pp-339

2006

DOI: https://doi.org/10.1109/CCC.2006.30

Abstract

Computer science

Algorithm design and analysis

Upper bound

Numerical analysis

Computational modeling

Traveling salesman problems

Fasteners

Polynomials

Mathematics

Encoding

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

Metrics

16 Record Views

Details

Title: On the complexity of numerical analysis
Creators: E Allender - Dept. of Comput. Sci., Rutgers, Piscataway, NJ
J Kjeldgaard-Pedersen
P Burgisser
P Miltersen
Publication Details: 21st Annual IEEE Conference on Computational Complexity (CCC'06), Vol.2006, pp.9 pp-339
Date published: 2006
Publisher: IEEE
Academic Unit: Computer Science (SAS)
Language: English
Resource Type: Conference proceeding
Identifiers: 991031654763404646