Hervé Fournier (IMJ, Paris Diderot)

Valiant a défini en 79 deux classes de complexité VP et VNP qui peuvent être vues comme des analogues des classes de complexité booléennes P et NP. Déterminer si VP=VNP est la question centrale de la complexité algébrique. Les travaux de Valiant montrent qu’une borne inférieure superpolynomiale sur la taille des circuits arithmétiques calculant le permanent permet de séparer VP de VNP.

À ce jour, la meilleure borne inférieure sur la taille des circuits calculant un polynôme de VNP est de l’ordre de n log( n ), ce qui est bien loin de l’objectif superpolynomial. Cependant, des bornes inférieures superpolynomiales ont été obtenues pour des classes restreintes de circuits. Nous présenterons la technique des dérivées partielles initiée par Nisan et Wigderson, puis étendue par Raz, et Kayal, permettant d’obtenir de tels résultats.