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

jeudi 27 novembre 2003

description logique d’un calcul, suite

Question 1. – Nous allons montrer que posT C ≡ T C.

(1) Montrer le lemme suivant : Soit τ contenant deux constantes c et d. Soit φ une formule existentielle de posT C, c’est à dire une formule construite avec des formules atomiques et des négations de formules atomiques en utilisant ∨, ∧, T C et ∃. Alors, dans les modèles de ¬c = d, φ est équivalente à une formule de la forme [T C_{x̄,x̄′}ψ(x̄, x̄′)]c̄, d̄ où ψ est une formule sans quantificateur.

(2) Soit τ contenant {S, <, min, max}. Sur les τ-structures ordonnées avec au moins deux éléments. Montrer que toute formule de posT C est équivalente à une formule de la forme [T C_{x̄,x̄′}ψ(x̄, x̄′)]m̄in, m̄ax où ψ est une formule sans quantificateur.

(3) Un uple d’éléments de la structure peut être vu comme l’entier dont il est l’écriture en base n. Quel uple représente ||A||^{r}? Soit d_{ψ}(ā, b̄) la longueur du plus petit chemin non vide défini par la formule ψ et reliant ā à b̄ quand il existe, et ∞ sinon. Montrer que d_{ψ}(ā, b̄) < ∞ ssi 0 < d_{ψ}(ā, b̄) ≤ ||A||^{r}, puis que ¬[T D_{x̄,ȳ}ψ(x̄, ȳ)]s̄, t̄ est équivalente à

||{v̄|d_{ψ}(s̄, v̄) < ∞}|| = ||{v̄|d_{(ψ(x̄,ȳ)∨¬ȳ=t̄)}(s̄, v̄) < ∞}||

Nous allons maintenant nous efforcer d’exprimer cette égalité par une formule de posT C.

(4) Pour toute formule φ(x_{1}, …, x_{r}, y_{1}, …, y_{r}) de posT C donner une formule ψ(x̄, ȳ, z_{1}, …, z_{r+1}) de posT C exprimant que d_{ϕ}(x̄, ȳ) ≤ z̄.

(5) En utilisant une définition inductive de la fonction g(x̄, ū) = ||{ȳ|d_{ϕ}(x̄, ȳ) ≤ ū}||, donner une formule χ_{ϕ}(x̄, ū, z̄, z̄′) de posT C exprimant que si g((x̄, ū) = z̄ alors g((x̄, ū + 1) = z̄′

(6) En déduire que pour toute formule du premier ordre φ(x̄, ȳ) il existe une formule ρ_{φ}(x̄, z̄) de posT C qui exprime que ||{ȳ|d_{ϕ}(x̄, ȳ) ≤ ∞}|| = z̄.

(7) Conclure

(8) Montrer le corollaire suivant : Soit τ contenant {S, <, min, max}. Sur les τ-structures ordonnées avec au moins deux éléments, toute formule de T C est équivalente à une formule de la forme [T C_{x̄,x̄′}ψ(x̄, x̄′)]m̄in, m̄ax où ψ est une formule sans quantificateur.

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 2. – 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 3. – Montrer que C_{1} ⊂ C_{2} ssi C′_{1} ⊂ C′_{2}.

Question 4. – 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 5. – 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 6. – 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 7. – 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 8. – Montrer que si L capture fortement C alors L capture C.

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

Question 10. – Montrer que Π_{1}^{1} capture fortement co − NP T IME.

Question 11. – Montrer que NP T IME = co − NP T IME ssi Σ_{1}^{1} = Π_{1}^{1}.

Question 12. – Montrer que NP T IME = co − NP T IME ssi Σ_{1}^{1} = SO.

Question 13. – Montrer que NLOGSP ACE = co − NLOGSP ACE.