ECCC-Report TR04-003https://eccc.weizmann.ac.il/report/2004/003Comments and Revisions published for TR04-003en-usMon, 12 Jan 2004 20:28:00 +0200
Paper TR04-003
| Valiant's model and the cost of computing integers |
Pascal Koiran
https://eccc.weizmann.ac.il/report/2004/003Let $\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.
Mon, 12 Jan 2004 20:28:00 +0200https://eccc.weizmann.ac.il/report/2004/003