M1, 2005–2006

Complexité structurelle – Partiel, correction

Exercice 1

⟹ : le langage L = {n en binaire ; 1^{n} ∈ T } est dans E^{T} donc dans E. Pour décider T dans P, sur l’entrée 1^{n} il suffit d’écrire n en binaire et de lancer l’algo E pour L. ⟸ : dans E, les appels à l’oracle sont au plus de taille 2^{O(n)}, donc on peut simuler l’algorithme P tout en restant dans E.

Exercice 2

Question 1 – Notons d’abord que pour tout C ⊆ A, tout mot x vérifiant ∃y ∈ C tel que f(x, y) = x ou f(y, x) = x est dans A. Cela montre l’inclusion ⊇.

Nous construisons maintenant l’ensemble C. Soit le graphe complet orienté dont les sommets sont les mots x de A ∩ {0, 1}^{n}, et l’arc entre x et y est dans la direction x vers y si f(x, y) = y et f(y, x) = y. Sinon on oriente l’arc arbitrairement.

La somme des degrés sortant est égale à la somme des degrés entrant, qui est égale au nombre d’arcs, soit k(k − 1)/2 où k est le nombre de sommets. Ainsi, il existe un sommet de degré sortant ≥ (k − 1)/2. On appelle y_{1} ce sommet et on considère le nouveau graphe dans lequel on a enlevé tous les fils de y_{1}. Ce nouveau graphe a au plus (k + 1)/2 sommets ; on peut recommencer avec lui pour trouver un sommet y_{2} de degré sortant ≥ ((k + 1)/2 − 1)/2. Et ainsi de suite.

À la fin, on obtient au plus n tels y_{i}, et il ne reste plus qu’un sommet dans le graphe, que l’on prend également : ainsi, on a un ensemble C d’au plus n + 1 sommets y_{i}. Par construction, tout sommet x du graphe initial est le fils d’un des y_{i}. Cela signifie que soit [f(x, y_{i}) = x et f(y_{i}, x) = x], soit [f(x, y_{i}) = y_{i} et f(y_{i}, x) = x] ou symétriquement. On a bien le résultat demandé.

Question 2 – On donne comme conseil l’ensemble C, qui est de taille O(n^{2}) (il contient au plus n + 1 mots de taille n). L’algorithme fonctionne alors ainsi : sur l’entrée x, pour tout y ∈ C on calcule f(x, y) et f(y, x). Si l’un des deux est x alors on accepte, sinon on rejette.

Question 3 – Soit A p-sélectif via f, et tel que SAT ≤ A. Ainsi, il existe g polynomiale telle que x ∈ SAT ⟺ g(x) ∈ A. Nous allons donner un algorithme polynomial pour SAT, utilisant comme d’habitude son auto-réductibilité. Entrée : ϕ(x_{1}, …, x_{k}).

– Pour i de 1 à k, faire – on calcule f(g(ϕ(x_{i} := 0)), g(ϕ(x_{i} := 1)))

– si le résultat est g(ϕ(x_{i} := 0)), alors ϕ := ϕ(x_{i} := 0), sinon ϕ := ϕ(x_{i} := 1).

– maintenant, ϕ n’a plus de variable ; on accepte si et seulement si ϕ est vraie. Si ϕ ∉ SAT, alors l’algorithme refuse toujours. Si ϕ ∈ SAT, l’algorithme trouve une affectation la satisfaisant.

Problème

Question 1 – Il suffit de montrer que NP^{DP} ⊆ Σ_{2} et le résultat suit par récurrence. En d’autres termes, il suffit de montrer que NP^{DP} ⊆ NP^{NP}. Si l’oracle DP est L = L_{1} \L_{2} avec L_{1} et L_{2} dans NP, alors on peut simuler l’appel à l’oracle L par un appel à L_{1} et un appel à L_{2}, ce qui conclut.

Question 2 – En combinant les deux étapes, on obtient coNP ⊆ NP/1 ⟹ Σ_{2} ⊆ DP. On conclut grâce à la question 1.

Question 3 – À partir d’une formule ϕ, en ajoutant des nouvelles variables on obtient facilement une formule ψ de taille plus grande qui est satisfaisable si et seulement si ϕ l’est. Ainsi, il suffit de fixer un majorant k (polynomial en n) sur la taille des requêtes à l’oracle, et au lieu de demander ϕ à l’oracle SAT, on demande ψ de taille k.

Question 4 – On veut simuler dans NP/1 le fonctionnement d’une machine NP M qui fait des appels à l’oracle SAT ∈ NP. Soit N_{1} une machine NP qui décide SAT. Puisque coNP ⊆ NP/1, on a par ailleurs une machine NP/1 N_{2} qui décide coSAT.

On simule M^{SAT} par une machine NP/1 de la façon suivante. Par la question 3, on peut supposer que tous les appels à l’oracle ont même taille k. À chaque appel à l’oracle pour savoir si x ∈ SAT, on lance d’abord N_{1} sur x. Si sur le chemin en cours, la réponse est oui, alors on sait que x ∈ SAT et on peut continuer la simulation de M^{SAT}. Si la réponse est non, alors on lance N_{2} sur x avec le conseil correspondant aux mots de taille k = |x|. Si la réponse de N_{2} sur le chemin courant est non, alors on rejette (on arrête ce chemin de calcul), sinon on sait que x ∉ SAT et on peut continuer la simulation de M^{SAT}.

La machine ainsi définie fonctionne avec un bit de conseil, et a un chemin acceptant si et seulement si M^{SAT} en a un.

Question 5 – On sait qu’il existe des langages Σ_{2}-complets (par exemple, SAT_{2}) ; ils sont de la forme

L = {x/(∃y)(∀z)(x, y, z) ∈ A]},

où A ∈ P et où les quantifications portent sur des mots de taille polynomiale. Il existe alors une réduction évidente de L au langage donné dans l’énoncé.

Question 6 – Si on connaît le bit de conseil, dans NP on peut décider L. On peut maintenant faire varier y, et à chaque fois appeler notre oracle L sur l’entrée (x, y), afin de faire une recherche dichotomique pour trouver le y′_{max} de l’énoncé : notre entrée est rejetée si et seulement si y′_{max} < y. Le nombre d’étapes est logarithmique en le nombre de y′ possibles, donc polynomial en n (c’est la taille de y′). Tout cela se fait donc dans P^{NP}.

Question 7 – On suppose d’abord que le conseil est 0, et on simule le calcul de la question 6 avec ce conseil. Cela nous donne un mot y′_{1}. On fait de même en supposant que le conseil est 1 : on obtient un mot y′_{2}. Il suffit maintenant de décider si (∀z)[(x, y′_{1}, z) ∈ A] ∨ (∀z)[(x, y′_{2}, z) ∈ A]. C’est un problème coNP qui se résoud en un appel à l’oracle supplémentaire. Ainsi, L ∈ P^{NP} et donc Σ_{2} ⊆ P^{NP} (par complétude de L) sous l’hypothèse coNP ⊆ NP/1.

Question 8 – Il est facile de construire une telle machine dans PLexMaxSat ⊆ Σ_{2}. Maintenant, la simulation de la question 4 permet de conclure.

Question 9 – A_{1} et A_{2} sont clairement dans NP.

Si ϕ ∈ LexMaxSat : ϕ ∈ A_{1} par définition de A_{1}. De plus, ϕ ∉ A_{2} : si l’une des deux simulations rejette, alors ϕ est rejetée ; sinon, l’une des deux renvoie le bon résultat x_{max}, l’autre un x_{2} plus petit, et x_{max} = max(x_{max}, x_{2}) se termine par 1.

Si ϕ ∉ LexMaxSat : si ϕ ∈ A_{1} alors l’une des deux simulations renvoie un mot x_{0} se terminant par 1. Il ne peut s’agir de x_{max}, sinon ϕ ∈ LexMaxSat. Ainsi, puisque ϕ est satisfaisable, l’autre simulation renvoie x_{max} qui se termine par 0. Or, puisque x_{0} < x_{max}, ϕ ∈ A_{2}, et donc ϕ ∉ A_{1} \ A_{2}. Évidemment, si ϕ ∉ A_{1} alors on a également ϕ ∉ A_{1} \ A_{2}.

Ainsi, LexMaxSat ∈ DP ce qui conclut par complétude de LexMaxSat.