Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > BLUM-SHUB-SMALE MODEL:
Reports tagged with Blum-Shub-Smale model:
TR04-003 | 22nd December 2003
Pascal Koiran

#### Valiant's model and the cost of computing integers

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

TR05-037 | 8th April 2005
Eric Allender, Peter Bürgisser, Johan Kjeldgaard-Pedersen, Peter Bro Miltersen