Skip to Main content Skip to Navigation

Valiant's model : from exponential sums to exponential products

Abstract : 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.
Document type :
Complete list of metadata

Cited literature [18 references]  Display  Hide  Download
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 11:09:13 AM
Last modification on : Saturday, September 11, 2021 - 3:19:07 AM


Files produced by the author(s)


  • HAL Id : hal-02102310, version 1



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⟩



Record views


Files downloads