Let $\tau(k)$ be the minimum number of arithmetic operations
required to build the integer $k \in \N$ from the constant 1.
A sequence $x_k$ is said to be ``easy to compute'' if
there exists a polynomial $p$ such that $\tau(x_k) \leq p(\log k)$
for all $k \geq ... more >>>

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