feuille de TD n^{o}9 – Complexité descriptive et théorie des modèles finis Natacha Portier

mardi 2 décembre 2003

description logique d’un calcul, suite

Parle t-on bien des mêmes classes de complexité ? Pour P T IME on définit : C est l’ensemble des langages L ⊂ 𝔸^{∗}, où 𝔸 est un alphabet, tels qu’il existe une machine de Turing déterministe qui accepte L en temps polynomial. C′ est l’ensemble des classes K de structures ordonnées sur le vocabulaire τ contenant < telles qu’il existe une machine de Turing déterministe acceptant K en temps polynomial.

On définit de même C et C′ pour LOGSP ACE, NLOGSP ACE, P T IME, NP T IME et P SP ACE.

Question 1. – Nous allons montrer que “via un codage, C ⊂ C′”, et réciproquement. Soit 𝔸 un alphabet et τ le vocabulaire {<} ∪ {P_{a}|a ∈ 𝔸} où les P_{a} sont des symboles de relations unaires. A un mot u_{1} … u_{n} sur 𝔸 on associe la structure K_{u} sur τ avec pour ensemble de base 1 < 2 < ⋯ < n et P_{a}(i) ssi u_{i} = a. Pour tout langage L soit K_{L} l’ensemble des K_{u} pour u ∈ L. Donner une formule qui caractérise K(𝔸^{∗}) et conclure. Faire la réciproque.

Question 2. – Montrer que C_{1} ⊂ C_{2} ssi C′_{1} ⊂ C′_{2}.

Question 3. – Montrer que :

(a) F O(IF P) ≡ F O(P F P) (ont le même pouvoir d’expression) sur les structures ordonnées ssi P T IME = P SP ACE (en théorie classique de la complexité)

(b) F O(IF P) ≡ Σ_{1}^{1} sur les structures ordonnées ssi P T IME = NP T IME (en théorie classique de la complexité)

(c) F O(IF P) ≡ SO sur les structures ordonnées ssi P T IME = NP T IME (en théorie classique de la complexité)

Question 4. – Montrer que :

(a) F O(DT C) ≤ F O(T C) ≤ F O(IF P) ≤ Σ_{1}^{1} ≤ F O(P F P)

(b) on n’a pas F O(DT C) ≡ F O(P F P)

Question 5. – Une logique L capture une classe de complexité C si pour tout τ contenant < et pour toute classe K de structures ordonnées sur τ on a : K ∈ C ssi K est axiomatisable dans L. Donner des exemples

Question 6. – Une logique L capture fortement une classe de complexité C si pour tout τ et pour toute structure classe K de structures sur τ on a : K ∈ C ssi K est axiomatisable dans L. Sur le vocabulaire vide, la classe des structures de cardinal pair n’est pas axiomatisable dans DT C. Qu’en est-il si on ajoute < au vocabulaire ? Qu’en conclure ?

Question 7. – Montrer que si L capture fortement C alors L capture C.

Question 8. – Montrer que Σ_{1}^{1} capture fortement NP T IME.

Question 9. – Montrer que Π_{1}^{1} capture fortement co − NP T IME. Question 10. – Montrer que NP T IME = co − NP T IME ssi Σ_{1}^{1} = Π_{1}^{1}. Question 11. – Montrer que NP T IME = co − NP T IME ssi Σ_{1}^{1} = SO. Question 12. – Montrer que NLOGSP ACE = co − NLOGSP ACE.