Complexite descriptive et theorie des modeles finis : le point de vue d'un
theoricien des modeles

par

Bruno POIZAT, Qaragandy Memlekettik Universiteti et Institut Girard Desargues


J'ai deja fait il y a quelques temps, et en ce lieu meme, une conference
avec un titre identique. Mais comme j'avais devant moi un public de
mathematiciens qui ne connaissaient pas leur alphabet jusqu'aux lettres N
et P , celle que je vais donner ici sera de nature bien differente.

Comme tout le monde ici le sait, la question P =? NP est un probleme de
nature combinatoire dont la solution se fait attendre ; son importance se
manifeste par le grand nombre de facons differentes dont on peut le
formuler.

Une de ces facons a ete decouverte il y a quelques trois lustres par Fagin,
qui a traduit la question voisine NP =? co-NP en termes de separation
d'enonces existentiels et universels du second ordre sur des structures
finies (j'espere egalement que les participants a cette rencontre sont
familiers de la notion de formule). Cela a donne l'espoir d'une approche
modele-theorique du probleme NP =? co-NP, et Fagin et ses fideles ont
produit differents resultats de separation d'enonces existentiels et
universels a quantifications monadiques (i.e. ou les predicats quantifies
sont des relations unaires seulement) ; bien que le contraire soit
regulierement affirme dans les introductions des articles ou ils sont
exposes, il ne me semble pas qu'ils aient la moindre signification en terme
d'algorithmie.

J'exposerai (brievement) les fondements de cette approche, et je tordrai le
cou a une legende, qu'on aime raconter dans les introductions des articles
cites, qui veut que la theorie des modeles du premier ordre ait un
caractere "local", par opposition a la theorie des modeles du second ordre.
Ce qui est exact, c'est que les resultats n'ont ete obtenus que dans des
contextes ou elle avait bien ce caractere local, quel que soit le sens
qu'on donne au mot "local" pourvu qu'il soit preserve par l'adjonction de
predicats unaires ; par contre, pour ce qui est des structures finies, la
logique du second ordre est interpretable dans celle du premier ordre
(c'est a peu pres evident), si bien qu'on ne peut esperer de methode
modele-theorique generale pour separer ces langages : ce qui les distingue,
c'est la taille des objets manipules, et la "logique" n'apporte pas une
formulation du probleme bien differente de l'originale ! J'enoncerai des
theoreme de Gaifman, de Hanf, et de Hanf-ordonne, qui precisent ce qu'on
entend par "local".

Un autre phénomène frappant, c'est que ces contextes favorables ont une
limite a l'infini, c'est-à-dire produisent des structures infinies ayant
des propriétés structurelles particulierement simple, disons stables ou
O-minimales. Cela ne fait que confirmer le sentiment que l'infini est plus
accessible que le fini arbitrairement grand, et que si le fini reste
cahotique, sans s'organiser a l'infini, la situation est sans espoir (de
meme que P =? NP !).

Mon expose sera une introduction au sujet pour ceux qui ne le connaissent
pas encore, et, je l'espere, une base de discussion pour les connaisseurs.