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

Cited literature [18 references]  Display  Hide  Download

https://hal-lara.archives-ouvertes.fr/hal-02102310
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 11:09:13 AM
Last modification on : Thursday, November 21, 2019 - 2:38:40 AM

File

RR2006-21.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02102310, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

19

Files downloads

41