Model Theory and Computational Complexity - Archive ouverte HAL Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 1997

Model Theory and Computational Complexity

(1) , (1)
1

Résumé

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.
Fichier principal
Vignette du fichier
RR1998-02.pdf (354.56 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-02101873 , version 1 (17-04-2019)

Identifiants

  • HAL Id : hal-02101873 , version 1

Citer

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⟩
19 Consultations
11 Téléchargements

Partager

Gmail Facebook Twitter LinkedIn More