Retour à l'index du GREYC

Séminaire Algorithmique

Site du CNRS

Séminaire Algorithmique

Le séminaire a lieu le mardi à 11 h 45 (sauf modification exceptionnelle), au campus Côte de Nacre, bâtiment Sciences 3, salle S3 351, 3ème étage.

Résumé du séminaire du Mardi 27 Janvier 2015

Les méthodes de dérivées partielles pour les bornes inférieures en complexité algébrique

par 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.

GREYC
Campus Côte de Nacre, boulevard du Maréchal Juin
BP 5186
14032 Caen Cedex
FAX : +33 (0)2 31 56 73 30
http://www.greyc.fr