Vers l’obtention de nouvelles bornes inférieures en complexité algébrique – VONBICA

Le problème P=NP est généralement considéré comme l'un des problèmes majeurs de l'informatique fondamentale. La difficulté d'obtenir des progrès sur ce problème a encouragé les chercheurs à se concentrer sur ses variantes. L'une d'elles apparaît en complexité arithmétique : peut-on prouver que certains polynômes explicites ne peuvent pas être calculés en effectuant seulement un nombre polynomial d'opérations arithmétiques ? L'espoir est que la robustesse des structures algébriques et les divers outils mathématiques qui s'y rapportent puissent aider à faire face à ces questions.
L'analogue de la conjecture de Cook dans ce domaine est la question de savoir si VP=VNP. Plus explicitement, nous voulons savoir s'il existe une séquence de circuits de taille polynomiale pour calculer le Permanent (ce polynôme peut être obtenu à partir du déterminant en remplaçant toutes les soustractions par des additions). La question est significative puisque Valiant a montré que si le permanent peut être calculé par de petits circuits, alors c'est aussi le cas pour tout polynôme VNP (c'est-à-dire tout polynôme dont les bits des coefficients peuvent être calculés efficacement). Il est largement conjecturé que cette existence ne devrait pas être possible (cela impliquerait autrement que P=NP dans le cadre booléen non uniforme). Cette question, posée par Valiant dès 1979, reste encore largement ouverte. Cependant, par rapport à sa contrepartie booléenne, de nombreux résultats prometteurs sont apparus ces dernières années pour tenter de la résoudre. L'objectif central de ce projet est de participer à l'avancée de ces résultats.