Return to search

Polynômes et coefficients

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.

Identiferoai:union.ndltd.org:CCSD/oai:tel.archives-ouvertes.fr:tel-00087399
Date07 July 2003
CreatorsMalod, Guillaume
PublisherUniversité Claude Bernard - Lyon I
Source SetsCCSD theses-EN-ligne, France
LanguageFrench
Detected LanguageFrench
TypePhD thesis

Page generated in 0.0016 seconds