Model Theory and Computational Complexity

Grégory Lafitte (1) , Jacques Mazoyer (1)

1 LIP - Laboratoire de l'Informatique du Parallélisme

Model theory has lately become a domain of interest to computer scientists. The reason is that model theory, and in particular its restriction to finite models, has led to some new results in computational complexity (e.g. NLOGSPACE=co-NLOGSPACE). In this report, firstly we present a survey of this theory and we focus on the descriptive complexity aspects and other links between computational complexity and model theory. Secondly, we extend some results of Grandjean and Lynch. We give a more precise logical characterization of complexity classes NTIME(n^d) for some d. This leads us to show applications of this result and to give openings made possible by this result.

Les informaticiens théoriques se sont récemment intéressés à la théorie des modèles. La raison est que la théorie des modèles, en particulier lorsque l'on se restreint à des modèles finis, a permis d'aboutir à de nouveaux résultats en complexité (e.g. NLOGSPACE=co-NLOGSPACE). Dans ce rapport, nous présentons premièrement une étude de cette théorie dans le but de présenter les notions de complexité descriptive et d'autres liens entre la complexité et la théorie des modèles. Deuxièmement, nous étendons des résultats de Grandjean et Lynch. Nous donnons une caractérisation logique plus précise des classes de complexité NTIME(n^d) pour un certain d. Enfin, nous montrons des implications de notre résultat et nous donnons différentes ouvertures rendues possibles grâce à ce résultat.

Mots clés: Computational Complexity; Games on Structures; Model Theory

Mots clés: Complexité de Calcul; Jeux sur des Structures; Théorie des Modèles

Domaines: Informatique [cs]

Grégory Lafitte, Jacques Mazoyer. Model Theory and Computational Complexity. [Research Report] LIP RR-1998-02, Laboratoire de l'informatique du parallélisme. 1997, 2+33p. ⟨hal-02101873⟩