On the Complexity of Numerical Analysis

Eric Allender; Peter Bürgisser; Johan Kjeldgaard-Pedersen; Peter Bro Miltersen

On the Complexity of Numerical Analysis

Eric Allender, Peter Bürgisser, Johan Kjeldgaard-Pedersen, Peter Bro Miltersen

Publikation: Bidrag til tidsskrift/Konferencebidrag i tidsskrift /Bidrag til avis › Tidsskriftartikel › Forskning

Abstract

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.

Originalsprog	Engelsk
Tidsskrift	Electronic Colloquium on Computational Complexity
Nummer	TR05-037
Sider (fra-til)	1-12
ISSN	1433-8092
Status	Udgivet - 2005

Citationsformater

@article{d2964a80b1b611dabee902004c4f4f50,

title = "On the Complexity of Numerical Analysis",

abstract = "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.",

author = "Eric Allender and Peter B{\"u}rgisser and Johan Kjeldgaard-Pedersen and Miltersen, {Peter Bro}",

note = "Paper id:: http://eccc.hpi-web.de/eccc-reports/2005/TR05-037/index.html",

year = "2005",

language = "English",

pages = "1--12",

journal = "Electronic Colloquium on Computational Complexity",

issn = "1433-8092",

number = "TR05-037",

}

TY - JOUR

T1 - On the Complexity of Numerical Analysis

AU - Allender, Eric

AU - Bürgisser, Peter

AU - Kjeldgaard-Pedersen, Johan

AU - Miltersen, Peter Bro

N1 - Paper id:: http://eccc.hpi-web.de/eccc-reports/2005/TR05-037/index.html

PY - 2005

Y1 - 2005

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

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

M3 - Journal article

SN - 1433-8092

SP - 1

EP - 12

JO - Electronic Colloquium on Computational Complexity

JF - Electronic Colloquium on Computational Complexity

IS - TR05-037

ER -

On the Complexity of Numerical Analysis

Abstract

Fingeraftryk

Citationsformater