Valiant's model and the cost of computing integers. - Archive ouverte HAL Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2004

Valiant's model and the cost of computing integers.

(1)
1

Résumé

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.
Fichier principal
Vignette du fichier
RR2004-01.pdf (287.91 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-02102106 , version 1 (17-04-2019)

Identifiants

  • HAL Id : hal-02102106 , version 1

Citer

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⟩
13 Consultations
96 Téléchargements

Partager

Gmail Facebook Twitter LinkedIn More