Résumé technique : Décidabilité de l'interprétabilité

1. Énoncé du problème

L'article traite de la complexité computationnelle et descriptive de la relation d'équivalence de la pp-bi-interprétabilité (bi-interprétabilité primitivement positive) dans le contexte des problèmes de satisfaction de contraintes (CSP).

La motivation centrale est la conjecture de Bodirsky-Pinsker, qui pose une dichotomie P vs NP-complet pour les CSP des reducts de premier ordre de structures homogènes bornées de façon finie. L'approche algébrique de cette conjecture repose sur l'idée que la complexité d'un CSP est déterminée par la classe d'isomorphisme topologique du clone de polymorphisme de la structure. Deux structures sont considérées comme équivalentes dans ce cadre si elles sont pp-bi-interprétables.

Alors que la décidabilité de la pp-interdéfinissabilité (égalité des clones de polymorphisme) avait été établie pour les reducts de premier ordre de structures Ramsey homogènes bornées de façon finie (Bodirsky, Pinsker et Tsankov, 2011), la décidabilité de la relation plus grossière de pp-bi-interprétabilité restait une question ouverte. De plus, pour la classe plus large des structures $\omega$-catégoriques, où la décidabilité algorithmique est impossible en raison de l'incountabilité, la complexité de cette relation d'équivalence n'avait pas été caractérisée à l'aide de la théorie descriptive des ensembles.

L'article cherche à déterminer si la relation d'équivalence de la pp-bi-interprétabilité est « raisonnable » dans deux sens :

1. Computationnellement : Est-elle décidable pour les structures situées dans le champ d'application de la conjecture de Bodirker-Pinsker ?
2. Descriptivement : La relation d'équivalence est-elle « lisse » (réductible de Borel à l'égalité sur les nombres réels) pour les structures $\omega$-catégoriques ?

2. Méthodologie

Les auteurs emploient une combinaison de théorie des modèles, d'algèbre universelle et de théorie descriptive des ensembles. La méthodologie procède à travers trois piliers techniques principaux :

A. Cores modèles-complets et existence constructive

Les auteurs utilisent le concept de core modèle-complet (model-complete core), une structure minimale unique (à isomorphisme près) qui est homomorphiquement équivalente à une structure $\omega$-catégorique donnée. Bien que l'existence de tels cores ait été connue auparavant via des preuves non constructives (reposant sur l'axiome du choix ou le théorème de compacité), les auteurs fournissent un algorithme constructif pour calculer le core modèle-complet pour les reducts de premier ordre de structures Ramsey homogènes bornées de façon finie.

• Ils définissent une « présentation optimale » d'un core, où l'image de tout endomorphisme intersecte toutes les orbites de la structure homogène sous-jacente.
• Ils utilisent des fonctions canoniques et la propriété de Ramsey pour calculer ces cores de manière algorithmique, évitant ainsi les arguments non constructifs de la théorie des ensembles.

B. La bi-définissabilité comme étape intermédiaire

Les auteurs introduisent la bi-définissabilité (conjugaison des clones de polymorphisme) comme une relation d'équivalence intermédiaire entre l'interdéfinissabilité et la bi-interprétabilité.

• La bi-définissabilité nécessite une bijection entre les domaines qui projette le clone de polymorphisme d'une structure sur l'autre via la conjugaison.
• Ils prouvent que décider la bi-définissabilité est décidable et que la relation est lisse.
• Crucialement, ils établissent que pour les structures sans algébricité (et les structures transitives dans le cas pp), la bi-définissabilité implique la bi-interprétabilité. Cela permet de transférer les résultats de décidabilité et de lissage de la bi-définissabilité, plus facile à manipuler, vers la bi-interprétabilité, plus complexe.

C. Cadre de la théorie descriptive des ensembles

Pour traiter la complexité de la bi-interprétabilité sur la classe de toutes les structures $\omega$-catégoriques, les auteurs encodent ces structures comme des éléments d'un espace borélien standard (spécifiquement, des séquences 0-1 isomorphes à $\mathbb{R}$). Ils analysent la relation d'équivalence en utilisant la réductibilité de Borel.

• Ils construisent une réduction de Borel de la relation de bi-définissabilité vers l'égalité sur $\mathbb{R}$ en associant à une structure $A$ la théorie du premier ordre d'une structure spécifique $E_{Pol(A)}$ dérivée de son clone de polymorphisme.
• Ils s'appuient sur les résultats de Coquand, Bodirsky et Junker concernant la relation entre l'isomorphisme topologique des groupes d'automorphismes/endomorphismes et la bi-interprétabilité.

3. Contributions clés et résultats

1. Décidabilité de la bi-interprétabilité (Théorème 4)

Les auteurs prouvent que le problème de décider si deux reducts de premier ordre $C, D$ de structures Ramsey homogènes bornées de façon finie sont fo/ep-bi-interprétables est décidable, à condition que leurs cores modèles-complets $C', D'$ soient sans algébricité.

• Extension à la pp-bi-interprétabilité : Si les structures sous-jacentes sont transitives (le groupe d'automorphisme agit avec une seule orbite sur le domaine), le résultat de décidabilité s'étend à la pp-bi-interprétabilité.
• Cela améliore le résultat de 2011 de Bodirsky, Pinsker et Tsankov, qui était limité à la pp-interdéfinissabilité.

2. Lissage de la bi-interprétabilité (Théorème 5)

Les auteurs établissent que la relation d'équivalence de l'ep-bi-interprétabilité est lisse sur la classe des cores modèles-complets $\omega$-catégoriques sans algébricité.

• De plus, la pp-bi-interprétabilité est lisse sur la sous-classe de ces structures qui sont également transitives.
• Cela implique que le problème de classification pour ces structures est aussi simple que possible dans la hiérarchie des relations d'équivalence boréliennes (réductible de Borel à l'égalité sur $\mathbb{R}$).

3. Calcul constructif des cores modèles-complets (Théorème 8)

L'article fournit la première preuve constructive de l'existence de cores modèles-complets pour les reducts de premier ordre de structures Ramsey homogènes bornées de façon finie.

• Ils présentent un algorithme qui, étant donné une telle structure, calcule une structure Ramsey homogène bornée de façon finie $A'$ et un reduct $C'$ qui est le core modèle-complet.
• Cela résout la dépendance aux preuves non constructives (théorème de compacité) présentes dans la littérature antérieure.

4. Résolution de l'écart entre bi-définissabilité et bi-interprétabilité

Les auteurs montrent que pour les structures sans algébricité, l'isomorphisme topologique des monoïdes d'endomorphismes (ou des clones de polymorphisme) implique la ep-bi-interprétabilité (Proposition 40). Cela comble une lacune dans les travaux précédents (Bodirsky et Junker, 2013) qui exigeaient des restrictions sur les endomorphismes constants. La condition de « non-algébricité » permet aux auteurs de lever ces restrictions.

4. Signification et affirmations

L'article affirme établir le caractère « raisonnable » de la relation d'équivalence de la pp-bi-interprétabilité, qui sous-tend l'approche algébrique moderne des CSP à domaine infini.

• Justification de l'approche algébrique : En montrant que la pp-bi-interprétabilité est décidable (sous des conditions légères) et lisse (au sens descriptif), les auteurs valident la stratégie consistant à classer les CSP sur la base de l'isomorphisme topologique des clones de polymorphisme plutôt que sur les structures individuelles.
• Faisabilité algorithmique : Le calcul constructif des cores modèles-complets fournit un outil pratique pour les chercheurs. Puisque les classifications de complexité nécessitent souvent de prétraiter un template pour obtenir son core modèle-complet, cet algorithme remplace les preuves d'existence non constructives par une procédure concrète.
• Portée : Les résultats s'appliquent à la grande majorité des structures considérées dans la conjecture de Bodirsky-Pinsker, particulièrement celles qui sont transitives et dépourvues d'algébricité. Les auteurs notent que bien que l'hypothèse de transitivité soit une restriction, elle couvre la plupart des dichotomies de complexité connues (par exemple, pour MMSNP, les graphes aléatoires et les ordres linéaires).

L'article ne prétend pas prouver l'intégralité de la conjecture de Bodirsky-Pinsker, mais renforce plutôt le fondement théorique sur lequel de telles preuves sont construites, en garantissant que les relations d'équivalence utilisées pour regrouper les structures sont bien comportées, tant sur le plan computationnel que descriptif.