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

mardi 28 octobre 2003

description logique d’un calcul

On veut montrer les théorèmes suivants : soit K une classe de structures ordonnées

(i) K ∈ LOGSP ACE iff K ∈ DT C
(ii) K ∈ NLOGSP ACE iff K ∈ T C
(iii) K ∈ P T IME iff K ∈ IF P
(iv) K ∈ NP T IME iff K ∈ Σ_{1}^{1}
(v) K ∈ P SP ACE iff K ∈ P F P

Question 1. – Définir les logiques citées.

Question 2. – Codage d’une structure et configuration d’une machine de Turing : définir le codage de la structure comme entrée de la machine, puis le codage d’une configuratione la fonction de transition dans une structure.

Question 3. – Montrer le lemme suivant :

Soit M une machine de Turing dont l’espace est borné en x^{d}. Il existe une formule du premier ordre φ_{start}(x̄) et des forules du premier ordre φ_{succ}(x̄, X) et ψ_{succ}(X, Y) où X et Y sont desprédicats telles que pour toute structure ordonnée A de cardinal n suffisemment grand et pour tout ā ∈ A^{d+2} on a :

(a) Si C_{0} est la configuration initiale de M sur l’entrée A alors A ⊧ φ_{start}(ā) iff ā ∈ C_{0}

(b) si M est déterministe et C est une configuration de M bornée par n^{d} alors A ⊧ φ_{succ}(ā, C) iff C a un successeur C′ borné par n^{d} et ā ∈ C′

(c) si C_{1} est une configuration de M bornée par n^{d} et C_{2} une relation (d + 2)-aire sur A alors A ⊧ ψ_{succ}(C_{1}, C_{2}) iff C_{2} est une configuration de M bornée par n^{d} qui succède à C_{1}.

Question 4. – Montrer le théorème suivant :

Soit K une classe de structures ordonnées sur le langage τ. Si K est dans P SP ACE alors K est axiomatisable dans F O(P F P).

Question 5. – En déduire le corollaire :

Soit K une classe de structures ordonnées sur le langage τ dans P SP ACE. Alors K est axiomatisable par une formule de F O(P F P) qui utilise une seule occurrence de P F P.

Question 6. – Montrer le théorème suivant :

Soit K une classe de structures ordonnées sur le langage τ. Si K est dans P T IME alors K est axiomatisable dans F O(IF P).

Question 7. – En déduire le corollaire :

Soit K une classe de structures ordonnées sur le langage τ dans P T IME. Alors K est axiomatisable par une formule de F O(IF P) qui utilise une seule occurrence de IF P.

Question 8. – Montrer le théorème suivant :

Soit K une classe de structures ordonnées sur le langage τ. Si K est dans NP T IME alors K est axiomatisable dans SO par une formule Σ_{1}^{1}.

Question 9. – Montrer le théorème suivant :

Soit K une classe de structures ordonnées sur le langage τ. Si K est dans LOGSP ACE alors K est axiomatisable dans F O(DT C).

Question 10. – Montrer le théorème suivant :

Soit K une classe de structures ordonnées sur le langage τ. Si K est dans NLOGSP ACE alors K est axiomatisable dans F O(T C).