Logique et Complexité
Cours de base (30 h de cours, 30h de TD)
Cours : Frank Wagner (wagner à igd.univ-lyon1.fr)
TD : Thomas Blossier (blossier à igd.univ-lyon1.fr)
Ce cours comprend deux parties distinctes, liées par la notion commune
de structure de première ordre. La première partie introduit les
notions de base de la théorie des modèles, domaine de la logique
mathématique qui analyse les structures et théories. La deuxième
partie étudie la notion de compléxité sur une structure quelconque, où
n'importe quelle opération du langage est aussi couteuse qu'une opération
booléenne.
Première Partie : Théorie des modèles
-
Structures. Equivalence élémentaire.
- Compacité de la logique de premier ordre.
- Elimination des quanteurs.
- Application aux corps réel-clos et algébriquement clos.
Deuxième Partie : Complexité
-
Fonctions calculables : termes et circuits booléens ; termes et
circuits sur une structure quelconque.
- Notion de calcul effectif ; le problème P = NP uniforme et
non-uniforme ; problèmes universels et NP-complets.
Lien avec l'elimination des quanteurs rapide.
Bibliographie
-
Wilfrid Hodges : A shorter model theory (Cambridge University
Press 1997)
- Bruno Poizat : Cours de théorie des modèles (Nur al-Mantiq
wal-Marifah 1985), traduction anglaise : A course in model theory
(Springer Verlag 2000)
- Bruno Poizat : (Nur al-Mantiq wal-Marifah 1985)