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

mardi 25 novembre 2003

description logique d’un calcul, suite

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

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

Question 1. – Soit posDT C l’ensemble des formules de DT C telles que DT C n’apparaisse que positivement dans la formule, i.e. pour chaque occurrence de DT C dans l’arbre de la formule, il y a un nombre pair de négations emboitées au dessus (i.e. sur le chemin jusqu’à la racine). On définit de même posT C.

Montrer que F O(DT C) ≡ F O(posDT C) (DT C et posDT C ont le même pouvoir d’expression), puis que F O(DT C) ≤ F O(posT C) (posT C est au moins aussi expressive que DT C, pour les modèles finis bien sur). En déduire que toute formule de DT C est équivalente à une formule de T C dans laquelle laquelle l’opération T C n’a aucune négation au dessus d’elle.

Question 2. – Soit M une machine qui travaille en temps polynomial et en espace logarithmique. Montrer qu’on peut demander à disposer des sous-programmes suivants :

(1) un sous-programme qui demande à la tête d’un ruban de travail donné de se déplacer jusqu’à la case la plus à droite visitée jusque là.

(2) un sous-programme qui demande l’effacement complet d’un ruban de travail donné.

(3) un sous-programme qui demande la copie d’un ruban de travail donné sur un autre ruban (choisi vide).

(4) un sous-programme qui, alors que le ruban d’entrée contient n symboles 1, écrit la représentation binaire de n^{d} sur un ruban de travail (initialisation d’un compteur).

Question 3. – Définition : Une machine représente fortement le fait K ∈ C si :

- M accepte K;

- tout calcul de M sur toute entrée A s’arrête sur s_{+} ou s_{−}, en particulier si M est déterministe alors M décide K;

- tout calcul de M sur toute entrée A remplit les critères de temps et d’espace de C. Pour toute formule φ dans DT C (resp. T C) montrer que la classe K des modèles or-

donnés de φ est dans LOGSP ACE (resp. NLOGSP ACE) et qu’il existe une machine M qui représente fortement cette appartenance.

En déduire que si K ∈ DT C (resp. K ∈ T C) alors K ∈ LOGSP ACE (resp. K ∈ NLOGSP ACE).

Question 4. – Soit K une classe de structures ordonnées. Montrer que :

(a) si K ∈ IF P alors K ∈ P T IME

(b) si K ∈ P F P alors K ∈ P SP ACE.

Question 5. – Soit K une classe de structures ordonnées. Montrer que :

(a) si K ∈ Σ_{1}^{1} alors K ∈ NP T IME

(b) si K ∈ SO alors K ∈ P SP ACE.

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

Question 8. – 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 9. – 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)