Valiant's model : from exponential sums to exponential products

Pascal Koiran (1) , Sylvain Perifel (1)

1 LIP - Laboratoire de l'Informatique du Parallélisme

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.

Mots clés: Algebraic complexity; Big products; Blum-Shub-Smale's model; Valiant's model

Mots clés: Complexité algébrique; Gros produits; Modèle BSS; Modèle de Valiant

Domaines: Informatique [cs]

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⟩