| Résume | La question de la séparation des classes de complexité fait actuellement face à un manque cruel de méthodes. En effet, de nombreux résultats, appelés barrières, démontrent que les méthodes de preuve connues ne permettront pas de répondre aux questions ouvertes principales. Le principal programme de recherche qui pourrait circonvenir aux barrières est le programme de complexité géométrique de K. Mulmuley. Celui-ci propose de montrer des résultats de séparation via des techniques de géométrie algébrique, et a été introduit après l'obtention d'un résultat de bornes inférieures une variante algébrique de PRAMs, un modèle de machines parallèles ad-hoc.
Cet exposé expliquera comment certaines méthodes récentes venant de la logique permettent de proposer une nouvelle approche à la question de la séparation. Basée sur une interpretation dynamique des programmes, celle-ci suggère une correspondance entre l'expressivité des modèles de calcul étudiés et certains invariants venant de théorie ergodique. Je présenterai également un travail en collaboration avec L. Pellissier, qui a consisté à relire la preuve de séparation ayant inspiré le programme de complexité géométrique via ce nouveau point de vue, faisant apparaitre le rôle de l'entropie topologique des systèmes dynamiques associés aux machines. Au-delà de renforcer l'intuition d'une correspondance entre classes de complexité et certaines classes de systèmes dynamiques, cette abstraction du résultat nous permet également de renforcer le résultat de séparation pour montrer que le problème maxflow (problème complet pour la classe P) n'est pas calculable efficacement par une machine parallèle travaillant avec des entiers. |
