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

mardi 4 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. – Définir les logiques T C et DT C. Montrer que T C est plus expressive que DT C.

Question 2. – Donner des formules φ_{+}(x, y, z), φ_{.}(x, y, z), φ_{2}(x, y) et φ_{log(universe)}(x) de DT C telles que pour toute structure ordonnée A avec A = {0, …, ||A|| − 1} et tous a, b, c de A on ait :

A mod φ_{+}[a, b, c]  ssi a + b = c
A mod φ_{.}[a, b, c]  ssi a.b = c
A mod φ_{2}[a, b]  ssi 2^{a} = b
A mod φ_{log(universe)}[a] ssi a = ⌈log ||A||⌉

Rappel : une structure ordonnée de cardinal n dans le langage τ est une structure dont les éléments sont 0, …, n−1 dans le langage τ augmenté de S, min, max, ≤ où S est le successeur, min = 0, max = n − 1 et ≤ est l’ordre sur les entiers.

Question 3. – Notation : si n = ||A|| et l = log n − 1 sont fixés, si m = m_{0}.2^{l−1} + m_{1}.2^{l−2} + ⋯ + m_{l−2}.2 + m_{l−1} alors [m] = m_{0} … m_{l−1} et m_{k} est le k^{e} chiffre binaire de [m].

Montrer qu’il exite des formules de DT C qui, pour toute structure ordonnée A, définissent les relations suivantes : One mk ssi m < 2^{l}, k < l et le k^{e} chiffre binaire de [m] est 1 Zero mk ssi m < 2^{l}, k < l et le k^{e} chiffre binaire de [m] est 0 One_{d} ūk ssi ū < 2^{l}, k < (d + 1).l et le k^{e} chiffre binaire de la concaténation [u_{0}] … [u_{d}] est 1 Zero_{d} ūk ssi ū < 2^{l}, k < (d + 1).l et le k^{e} chiffre binaire de la concaténation [u_{0}] … [u_{d}] est 0 Equal_{d} ūkū′ ssi ū, ū′ < 2^{l}, k < (d+1).l et les mots [u_{0}] … [u_{d}] et [u′_{0}] … [u′_{d}] diffèrent seulement à la k^{e} position ou pas du tout.

On notera ces formules φ_{one}(x, z), φ_{zero}(x, z), φ_{d−one}(x̄, z) et φ_{d−equal}(x̄, z, x̄′).

Question 4. – En supposant pour simplifier que τ est réduit à un symbole R de relation binaire, en déduire le lemme :

Soit M une machine dont l’espace est borné en d. log. Alors il existe des formules χ_{start}(x̄) du premier ordre et χ_{succ}(x̄, x̄′) de DT C telles que pour toute structure ordonnée suffisemment grande et de langage τ et pour tout ā dans A :

(a) A ⊧ χ_{start}[ā] ssi ā est la configuration de départ.

(b) Pour toute configuration ā bornée en espace par (d. log ||A||) et pour tout b̄, A ⊧ χ_{succ}[ā, b̄] ssi b̄ est une configuration successeur de ā bornée en espace par (d. log ||A||).

Question 5. – Montrer que si K ∈ LOGSP ACE alors K ∈ DT C.

Question 6. – Montrer que si K ∈ NLOGSP ACE alors K ∈ T C.

Question 7. – 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 DT C et posDT C ont le même pouvoir d’expression, puis que 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 8. – 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 9. – 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 10. – 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 11. – 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.