Programme de l’UE

Prouver des bornes inférieures sur la complexité algorithmique de problèmes spécifiques est souvent très difficile.  Par exemple, la question « P=NP ? » est de cette forme: il s’agit d’obtenir une borne inférieure superpolynomiale sur la complexité en temps du problème SAT (ou de manière équivalente sur la complexité de n’importe quel problème NP-complet).  Etant donnée la difficulté de ce problème et d’autres problèmes de ce type, on a proposé des modèles de calculs algébriques, variantes des modèles booléens « standards »; et on espère que les questions analogues soient plus abordables dans ces nouveaux modèles.

Les deux principales versions algébriques du problème « P=NP ? » sont dûes à Valiant et à Blum-Shub-Smale, et sont toujours ouvertes. Par exemple, le contenu algorithmique du problème « P=NP ? » dans le modèle de Blum-Shub-Smale sur le corps des nombres réels est le suivant: étant donné un polynôme dedegré 4 en n variables, peut-on décider s’il admet une racine réelle en un nombre d’opérations arithmétiques et de comparaisons polynomial en n ? Les meilleurs algorithmes connus à ce jour effectuent un nombre d’opérations exponentiel en n.

Dans le modèle de Valiant on ne s’intéresse pas à des problèmes de décision mais à l’évaluation de polynômes. Le contenu algorithmique de la question VP=VNP peut être formulé ainsi: est-il possible d’évaluer le permanent d’une matrice en un nombre d’opérations arithmétiques polynomial en la taille de cette matrice ?

On présentera ces deux modèles de calcul et des approches proposées pour aborder les versions correspondantes du problème P=NP:

  • conjecture tau de Shub et Smale: n! (ou un multiple) ne peut pas se calculer en un nombre d’opérations arithmétiques polynomial en log n
  • La version de cette conjecture sur le nombre de racines entières des polynômes donnés par circuits (qui est supposé polynomial en la taille du circuit).
  • La non généralisation aux racines réelles (polynômes de Chebyshev, exemple de Borodin-Cook).
  • Une version réelle pour les sommes de produits de polynômes creux.

On présentera également des résultats sur la réduction de profondeur pour les circuits arithmétiques, certains anciens (Muller-Preparata, Valiant-Skyum-Berkowitz-Rackoff), d’autres plus récents (Agrawal-Vinay).  Ces résultats sont non seulement intéressants du point de vue du calcul parallèle, mais aussi comme on le verra pour les bornes inférieures.

Prerequis: Il s’agit d’un cours de complexité donc un certain goût pour ce sujet et les connaissances acquises à l’occasion d’un premier cours (par exemple, le cours de complexité algorithmique de M1) ne peuvent pas faire de mal. Mais il n’y aura pas de besoin de connaissances specialisées dans le domaine car le cours porte sur des modèles de calcul alternatifs à la traditionnelle machine de Turing. Si nécessaire, quelques rappels de complexite booléenne seront faits.

Modalités d’examen : exposé sur un article (petit rapport + présentation orale) et examen écrit « classique » à la fin.

Intervenant

  • Pascal Koiran, Pr. ENS Lyon