Model Theory and Computational Complexity

Abstract : 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.
Document type :
Reports
Complete list of metadatas

Cited literature [26 references]  Display  Hide  Download

https://hal-lara.archives-ouvertes.fr/hal-02101873
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 9:08:43 AM
Last modification on : Friday, May 17, 2019 - 1:39:22 AM

File

RR1998-02.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02101873, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

2

Files downloads

4