On the Complexity of Numerical Analysis

Complexity of Boolean Functions

计算机科学;物理学;物理学

Eric Allender ; Johan Kjeldgaard-Pedersen ; Peter Bu¨rgisser ; Peter Bro Miltersen

Others  :  http://drops.dagstuhl.de/opus/volltexte/2006/613/pdf/06111.MiltersenPeterBro.Paper.613.pdf
PID  :  6437

学科分类：计算机科学（综合）

来源: CEUR

【 摘 要 】

We study two quite different approaches to understand- ing the complexity of fundamental problems in numerical analysis. We show that both hinge on the question of under- standing 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