__
TR04-003 | 22nd December 2003 00:00
__

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

**Abstract:**
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 1$.

It is natural to conjecture that sequences such as

$\lfloor 2^n \ln 2 \rfloor$ or $n!$ are not easy to compute.

In this paper we show that a proof of this conjecture for

the first sequence would imply a superpolynomial lower bound

for the arithmetic circuit size of the permanent polynomial.

For the second sequence,

a proof would imply a superpolynomial lower bound

for the permanent or separate P from PSPACE.