Projet ANR-13-BS02-0001 – CompA : Complexité algébrique
Programme : Blanc - SIMI 2 - Science informatique et applications (Blanc SIMI 2)
Année de financement : 2013
Coordinateur du projet : Monsieur KOIRAN Pascal (Laboratoire de l'Informatique du Parallélisme)
Partenaires : Laboratoire public; Laboratoire public
Montant : 346811.0 euros
Durée : 48 mois
Résumé : Complexité algébriqueUne version algébrique du problème «P= NP ?«
Comprendre les possibilités et les limites d'un modèle de calcul algébriqueLe problème «P = NP ?« est largement reconnu comme le problème ouvert le plus important en informatique théorique. Etant donné la difficulté du problème, on en a proposé plusieurs version algébriques avec l'espoir qu'elles soient plus abordables que le problème initial. Notre  projet porte sur l'une de ces versions, connues sous le nom  «VP = VNP ?«. Ce problème a été proposé par Leslie Valiant à la fin des années 1970. Pour le résoudre il faut trouver une famille de polynômes «explicite« qui ne peut pas être évaluée efficacement (en un nombre polynomial d'opérations arithmétiques). Des candidats naturels existent, par exemple le permanent de matrices, mais on ne sait pas montrer qu'ils sont réellement difficiles à évaluer.
Des bornes inférieures par des méthodes algébriquesLe modèle de calcul sous-jacent au problème «VP=VNP ?« est algébrique puisque les opérations de base du modèles sont les opérations arithmétiques (addition et multiplication). Par contre les modèles traditionnels sont booléens, ce'st à dire que les opérations de base sont booléennes (et logique, négation,...). Nous comptons exploiter le caractère algébrique du modèle pour développer de nouvelles techniques de preuves de bornes inférieures (c'est à dire montrer qu'un certain problème ne peut pas être résolu efficacement dans notre modèle). Pour cela nous comptons utiliser des outils classiques dans l'érude des bornes inférieures, comme la combinatoire  ou l'algèbre linéaire, mais aussi des outils algébriques (théorie des représentations) et géométriques (géométrie algébrique, voire géométrie convexe).
Résumé de la soumission : Le problème "P=NP ?" est largement reconnu comme le principal problème ouvert en informatique théorique. Etant donné la difficulté de ce problème , on en  a proposé des versions algébriques en espérant que des méthodes géométriques ou algébriques seront plus faciles à appliquer.L'objectif principal de ce projet est d'avancer dans la compréhension du problème "VP = VNP ?". Cette version algébrique du problème "P=NP ?" a été proposée par Leslie Valiant a la fin des années 1970. Dans le modèle de Valiant, on étudie la complexité de l'évaluation des polynômes. Le contenu algorithmique de ce problème peut être résumé en une phrase : est-il possible d'évaluer le permanent d'une matrice n fois n en un nombre d'opérations arithmétiques polynomial en n ? Le permanent est un polynôme en les n*n entrées de la matrice qui est (superficiellement) similaire au déterminant, la seule différence étant que seuls des signes positifs apparaissent dans son expansion comme une somme de n! termes. Cette question peut être formalisée à l'aide du modèle de calcul des circuits arithmétiques. On conjecture généralement que cette question admet une réponse négative. Notons que comme dans la théorie classique de la NP-complétude, on peut remplacer le permanent par n'importe quel problème NP-complet dans l'énoncé de ce problème.Ces dernières années, le problème "VP=VNP ?" a été l'objet d'un surcroît d'attention de la part des chercheurs en complexité algorithmique.Un objectif important du projet est de contribuer à cet effort en développant des outils qui pourraient un jour conduire à une solution du problème; et d'obtenir des bornes inférieures pour des classes restreintes de circuits arithmétiques. De tels résultats partiels sont très utiles pour progresser dans la compréhension du problème. Nous ne négligerons pas non plus certains problèmes directement liés aux bornes inférieures pour les circuits arithmétiques, comme par exemple la dérandomisation du test d'identité polynomiale.L'étude des propriétés structurelles des circuits arithmétiques est une seconde direction de recherche. On peut citer en exemple les résultats classiques de parallélisation obtenus dans les années 70 et 80 ainsi que les résultats plus récents sur la "réduction à la profondeur 4" (ces derniers ont été obtenus d'abord par Agrawal et Vinay, puis Koiran). D'autres exemples sont fournis par les travaux de Toda et Malod sur la caractérisation de classes de complexité algébriques par divers types de circuits arithmétiques : circuits multiplicativement disjoints, circuits "gauches" (skew, en anglais) ou "faiblement gauches" , programmes à branchements...
Résultats : Parmi les résultats obtenus pendant les premiers 18 mois du projet on peut citer:
- L'obtention de bornes inférieures optimales pour le calcul des polynômes symétriques élémentaires de petit degré. Ce résultat est basé sur la méthode des dérivées partielles «shiftées« et étend les résultats obtenus par Nisan et Wigderson dans les années 1990.
- La proposition d'un modèle de calcul simple: les sommes de puissances de polynômes de petit degré en une variable. Nous voyons ce modèle comme un «banc d'essai« pour le test de nouvelles idées dans un cadre relativement simple.
Perspectives : Nous comptons développer de nouvelles méthodes pour aller au delà de la méthode qui a obtenu les meilleurs succès récents, à savoir la méthode des dérivées partielles shiftées. Nous comptons tester nos idées sur le modèle en une variable mentionné ci-dessus; les méthodes à base d'interpolation polynomiale semblent particulièrement prometteuses.
Publications et brevets : Pendant les 18 premiers mois du projet nous avons publiés 3 articles dans des revues scientifiques, et 4 dans des conférences. La liste complète de nos pulbications est disponible sur le site web du projet.