Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, Epiciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
Skip to Main content Skip to Navigation
Reports

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 from the constants 1 and 2. A sequence (x_k) is said to be ``easy to compute'' if tau(x_k) is bounded by a polynomial function of log(k). 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 P different from PSPACE.
Document type :
Reports
Complete list of metadata

https://hal-lara.archives-ouvertes.fr/hal-02102106
Contributor : Colette ORANGE Connect in order to contact the contributor
Submitted on : Wednesday, April 17, 2019 - 9:14:24 AM
Last modification on : Saturday, September 11, 2021 - 3:19:16 AM

File

RR2004-01.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02102106, version 1

Collections

Citation

Pascal Koiran. Valiant's model and the cost of computing integers.. [Research Report] LP RR-2004-01, Laboratoire de l'informatique du parallélisme. 2004, 2+13p. ⟨hal-02102106⟩

Share

Metrics

Record views

12

Files downloads

78