Valiant's model : from exponential sums to exponential products - Archive ouverte HAL Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2006

Valiant's model : from exponential sums to exponential products

(1) , (1)
1

Résumé

We study the power of big products for computing multivariate polynomials ina Valiant-like framework. More precisely, we define a new class VΠP0 as the setof families of polynomials that are exponential products of easily computablepolynomials. We investigate the consequences of the hypothesis that thesebig products are themselves easily computable. For instance, this hypothesiswould imply that the nonuniform versions of P and NP coincide. Our mainresult relates this hypothesis to Blum, Shub and Smale’s algebraic version of Pversus NP. Let K be a field of characteristic 0. Roughly speaking, we show thatin order to separate PK from NPK using a problem from a fairly large class of“simple” problems, one should first be able to show that exponential productsare not easily computable. The class of“simple”problems under consideration isthe class of NP problems in the structure (K,+,−,=), in which multiplicationis not allowed.
Cet article étudie la puissance des gros produits pour le calcul de polynômes à plusieurs variables dans le cadre de la théorie de Valiant. Plus précisément, nous définissons pour cela une nouvelle classe VΠP0 de familles de polynômes : il s’agit des produits de taille exponentielle de polynômes facilement calculables.Nous étudions les conséquences de l’hypothèse que ces gros produits sont eux-mêmes facilement calculables. Par exemple, cela impliquerait que les versions non-uniformes de P et NP coïncident. Le résultat principal est un lien avec les classes algébriques P et NP du modèle BSS sur un corps K de caractéristique nulle. On pourrait l’énoncer ainsi : si nous voulons séparer PK de NPK grâce à des problèmes issus d’un ensemble important de problèmes « simples », il faut d’abord être capable de montrer que nos gros produits ne sont pas facilement calculables. L’ensemble des problèmes « simples » en question est NP sur la structure (K,+,−,=), dans laquelle la multiplication n’est pas autorisée.
Fichier principal
Vignette du fichier
RR2006-21.pdf (1.02 Mo) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

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

Identifiants

  • HAL Id : hal-02102310 , version 1

Citer

Pascal Koiran, Sylvain Perifel. Valiant's model : from exponential sums to exponential products. [Research Report] LIP RR-2006-21, Laboratoire de l'informatique du parallélisme. 2006, 2+10p. ⟨hal-02102310⟩
6 Consultations
58 Téléchargements

Partager

Gmail Facebook Twitter LinkedIn More