On the Complexity of Numerical Analysis

Peter Bro Miltersen; Johan Kjeldgaard-Pedersen; Peter Burgisser; Eric Allender

On the Complexity of Numerical Analysis

Peter Bro Miltersen, Johan Kjeldgaard-Pedersen, Peter Burgisser, Eric Allender

Publikation: Bidrag til bog/antologi/rapport/proceeding › Konferencebidrag i proceedings › Forskning › peer review

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 is greater than 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.

Originalsprog	Engelsk
Titel	Proceedings of the 21st Annual IEEE Conference on Computational Complexity
Antal sider	9
Forlag	IEEE Computer Society Press
Publikationsdato	2006
Sider	331-339
Status	Udgivet - 2006
Begivenhed	IEEE Conference on Computational Complexity - Prague, Tjekkiet Varighed: 17 dec. 2010 → … Konferencens nummer: 21

Konference

Konference	IEEE Conference on Computational Complexity
Nummer	21
Land/Område	Tjekkiet
By	Prague
Periode	17/12/2010 → …

Citationsformater

@inproceedings{e41267f0255d11dcbee902004c4f4f50,

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 is greater than 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. ",

keywords = "computional complexity, numerical analysis",

author = "Miltersen, {Peter Bro} and Johan Kjeldgaard-Pedersen and Peter Burgisser and Eric Allender",

year = "2006",

language = "English",

pages = "331--339",

booktitle = "Proceedings of the 21st Annual IEEE Conference on Computational Complexity",

publisher = "IEEE Computer Society Press",

note = "IEEE Conference on Computational Complexity ; Conference date: 17-12-2010",

}

TY - GEN

T1 - On the Complexity of Numerical Analysis

AU - Miltersen, Peter Bro

AU - Kjeldgaard-Pedersen, Johan

AU - Burgisser, Peter

AU - Allender, Eric

N1 - Conference code: 21

PY - 2006

Y1 - 2006

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 is greater than 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.

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 is greater than 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.

KW - computional complexity, numerical analysis

M3 - Article in proceedings

SP - 331

EP - 339

BT - Proceedings of the 21st Annual IEEE Conference on Computational Complexity

PB - IEEE Computer Society Press

T2 - IEEE Conference on Computational Complexity

Y2 - 17 December 2010

ER -

On the Complexity of Numerical Analysis

Abstract

Konference

Fingeraftryk

Citationsformater