Polynômes et coefficients

Valiant defines algebraic analogues of the classes P and NP. We characterize the classes VP and VQP, yielding a simplified proof of VNP = VNPe and of the VQP-completeness of the determinant, and a proof of a conjecture by Bürgisser. The classes VPo and VNPo, defined without arbitrary constants, yield a link between the complexity of a polynomial and that of its coefficient function: VNPo is stable for the operation of taking coefficient functions; claiming that this holds for VPo is equivalent to VPo = VNPo. For polynomials of unbounded degree, one needs efficient computations of binomial coefficients, which can be done in positive characteristic but are unlikely in characteristic 0. At last we study the related problem of the effect of derivation on complexity. After a new proof of a result by Kaltofen (the number of variables matters more than the derivation order) we show how to simultaneously compute partial derivatives.Valiant définit des analogues algébriques des classes P et NP. Nous caractérisons les classes VP et VQP, d'où une preuve simplifiée de VNP = VNPe et de la VQP-complétude du déterminant, et la preuve d'une conjecture de Bürgisser. Les classes VPo et VNPo, définies sans constantes arbitraires, donnent facilement un lien entre la complexité d'un polynôme et celle de sa fonction coefficient: VNPo est stable par passage à la fonction coefficient et réciproquement; supposer ce résultat pour VPo est équivalent à VPo = VNPo. Pour traiter le cas du degré non borné, il faut un calcul rapide des coefficients binomiaux, faisable en caractéristique positive et peu probable en caractéristique 0. Nous étudions enfin un problème lié: l'effet de la dérivation sur la complexité. Nous retrouvons le résultat de Kaltofen (le nombre de variables fait exploser la taille plus que l'ordre de dérivation) et donnons un calcul simultané des dérivées partielles