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

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 :
Complete list of metadata
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


Files produced by the author(s)


  • HAL Id : hal-02102106, version 1



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⟩



Record views


Files downloads