Abstract FR:

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 facielement 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 Katofen (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