Bornes de complexité générales pour les systèmes dynamiques finis – ALARICE

Les réseaux d'automates sont des modèles généraux d'entités en interaction, qui présentent des comportements collectifs "complexes". Lier les règles locales suivies par les entités, l'architecture des interactions, et la dynamique globale, est ce qui motive la communauté. ALARICE a pour objectif de comprendre ces liens au travers du cadre formel de la complexité algorithmique. Ce point de vue renouvelé explique pourquoi certaines bornes structurelles de la littérature restent lâches, malgré des efforts considérables : les inférences en jeu impliquent des décisions algorithmiquement complexes. Notre projet repose sur de premiers résultats prometteurs obtenus par les membres du consortium, et comporte trois volets. 1- Révéler des métathéorèmes de la forme "toute question non-triviale de type X exprimée en logique Y est Z-difficile" avec X comme "étant données les règles locales, question sur le graphe de la dynamique", Y parmi {FO,MSO,...} et Z parmi {P,NP,...}. Nous avons décroché un tel résultat "à la Rice", présenté à STACS'2021 (Y=FO, Z=NP), avec une technique de preuve basée sur du pompage abstrait, utilisant les outils de la théorie des modèles finis pour construire des métaréductions. 2- Caractériser la complexité formelle de nouveaux problèmes naturels, en particulier en lien avec l'architecture du réseau. Obtenir une compréhension mature des constructions est une étape préliminaire pour aller vers des métaénoncés. 3- Transférer ces connaissances à d'autres modèles de calcul, par des simulations strictes agissant comme des réductions. Notre consortium est construit autour d'un noyau d'expertise sur les réseaux d'automates, la complexité et la simulation. Il a pour but d'adjoindre des expertises additionnelles fortes sur les domaines connexes (théorie des modèles finis, dualisation de treillis, paramétrisation de graphes), afin de nourrir les articulations fécondes récemment découvertes.