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

mardi 9 décembre 2003

Problèmes d’optimisation

Un problème d’optimisation NPTIME est un quadruplet Q = (K, F, c, μ) où – K est une classe de structures (sur un vocabulaire fixé), les structures d’entrée

– pour A ∈ K, F (A) est l’ensemble des solutions pour A, ces solutions sont des parties de A^{s} (pour un s indépendant de A) ; de plus, {(A, S) | A ∈ K, S ∈ F (A)} est décidable en temps polynomial,

– c est une fonction calculable en temps polynomial de {(A, S) | A ∈ K, S ∈ F (A)} dans ℕ,

– μ ∈ {min, max}. On définit opt_{Q}(A) = μ{c(A, S) | A ∈ K, S ∈ F (A)}. Un problème d’optimisation Q est dit polynomialement borné (PB) si opt_{Q}(A) = |A|^{O(1)}. Un problème d’optimisation NPTIME Q est dit définissable au premier ordre si il existe φ(x̄, Ȳ) ∈ FO tel que pour toute structure A,

opt_{Q}(A) = μR̄|{ā ∈ A | A ⊧ φ(ā, R̄)}|.

Question 1. – Montrer que MAX-CUT et MIN-COVER sont définissables au premier ordre.

Question 2. – Montrer qu’un problème d’optimisation est borné polynomialement si et seulement si il est définissable au premier ordre (pour le sens difficile, on pourra introduire un prédicat d’arité k, cet entier k vérifiant opt_{Q}(A) ⩽ |A|^{k}).

Question 3. – Rappeler pourquoi toute formule du type ∃X̄φ avec φ ∈ FO est équivalente à une formule ∃Ȳ ψ avec ψ ∈ Π_{2} (par skolemisation). En déduire MAX PB = MAX FO = MAX Π_{2} et MIN PB = MIN FO = MIN Σ_{2}.

Question 4. – Montrer que MIN Π_{1} = MIN Σ_{2} et MIN Σ_{0} = MIN Σ_{1}.

Question 5. – Montrer que MIN CHROMATIC NUMBER est dans MIN Π_{1}.

Question 6. – Montrer que MIN CHROMATIC NUMBER n’est pas dans MIN Σ_{0}. La hiérarchie de minimisation est donc composée de deux niveaux exactement

MIN Σ_{0} = MIN Σ_{1} ⊊ MIN Π_{1} = MIN Σ_{2}.

Question 7. – Montrer que MAX Σ_{2} = MAX Π_{1} ; on introduira pour cela un prédicat supplémentaire destiné à interpréter des témoins pour le premier bloc de quantificateurs existentiel. En déduire que la hiérarchie de maximisation est composée de quatre niveaux au plus

MAX Σ_{0} ⊂ MAX Σ_{1} ⊂ MAX Π_{1} ⊂ MAX Π_{2}.

Question 8. – Montrer que les inclusions précédentes sont strictes.