On the Complexity of Numerical Analysis

Prague, Czech Republic July 16-July 20

DOI Bookmark:

http://doi.ieeecomputersociety.org/10.1109/CCC.2006.30

21st Annual IEEE Conference on Compu ...

	This Article
	PURCHASE ARTICLE: $19 PDF HTML IEEE Xplore Subscribers
	Share
	Email this Article to a friend
	Bibliographic References
	ASCII Text BibTex RefWorks Procite/RefMan/Endnote
	Add to:
	Digg Furl Spurl Blink Simpy Google Del.icio.us Y!MyWeb
	Search
	Similar Articles Articles by Eric Allender Articles by Peter Burgisser Articles by Johan Kjeldgaard-Pedersen Articles by Peter Bro Miltersen

	ASCII Text	x
	Eric Allender, Peter Burgisser, Johan Kjeldgaard-Pedersen, Peter Bro Miltersen, "On the Complexity of Numerical Analysis," Computational Complexity, Annual IEEE Conference on, pp. 331-339, 21st Annual IEEE Conference on Computational Complexity (CCC'06), 2006.

	BibTex	x
	@article{ 10.1109/CCC.2006.30, author = {Eric Allender and Peter Burgisser and Johan Kjeldgaard-Pedersen and Peter Bro Miltersen}, title = {On the Complexity of Numerical Analysis}, journal ={Computational Complexity, Annual IEEE Conference on}, volume = {0}, year = {2006}, issn = {1093-0159}, pages = {331-339}, doi = {http://doi.ieeecomputersociety.org/10.1109/CCC.2006.30}, publisher = {IEEE Computer Society}, address = {Los Alamitos, CA, USA}, }

	RefWorks Procite/RefMan/Endnote	x
	TY - CONF JO - Computational Complexity, Annual IEEE Conference on TI - On the Complexity of Numerical Analysis SN - 1093-0159 SP331 EP339 A1 - Eric Allender, A1 - Peter Burgisser, A1 - Johan Kjeldgaard-Pedersen, A1 - Peter Bro Miltersen, PY - 2006 KW - null VL - 0 JA - Computational Complexity, Annual IEEE Conference on ER -

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

Peer Review Notice | Give Us Feedback

Usage of this product signifies your acceptance of the Terms of Use.