M1, 2005–2006

Complexité structurelle – Partiel Lundi 27 mars, 13h30 – 15h30

Exercice 1

On rappelle que E = DTIME(2^{O(n)}). Soit T unaire. Montrer que E^{T} = E ⟺ T ∈ P.

Exercice 2

Un langage A est dit p-sélectif s’il existe une fonction f calculable en temps polynomial (f est appelée la fonction de sélection), telle que pour tout x, y ∈ {0, 1}^{∗}, on ait :

– f(x, y) = x ou f(x, y) = y;

– si x ∈ A ou y ∈ A alors f(x, y) ∈ A. Question 1 – Soit A un langage p-sélectif avec fonction de sélection f. Montrer que pour tout n, il existe un ensemble C ⊆ A ∩ {0, 1}^{n} tel que |C| ≤ n + 1 et

A ∩ {0, 1}^{n} = {x; |x| = n et ∃y ∈ C tel que f(x, y) = x ou f(y, x) = x}.

Question 2 – Montrer qu’un langage p-sélectif est dans P/poly. (Ko, 1983)

Question 3 – Montrer que s’il existe un langage p-sélectif NP-difficile, alors P = NP.

Problème

Le but de ce problème est de montrer l’implication suivante^{1} :

coNP ⊆ NP/1 ⟹ PH ⊆ DP.

On rappelle que la classe DP est celle des langages qui sont l’intersection d’un langage NP et d’un langage coNP, ou de manière équivalente, qui sont la différence de deux langages NP. Par ailleurs, NP/1 est la classe des langages NP avec un conseil de longueur 1. L’ordre utilisé sur les mots booléens est l’ordre lexicographique. Enfin, PH désigne la hiérarchie polynomiale : PH = ∪_{i}Σ_{i}, avec

Σ_{0} = P, et Σ_{i+1} = NP^{Σ_{i}}.

Question 1 – Montrer que Σ_{2} ⊆ DP ⟹ PH ⊆ DP.

Pour montrer le résultat annoncé au début du problème, nous allons procéder en deux étapes : d’abord, nous allons montrer que coNP ⊆ NP/1 ⇒ Σ_{2} ⊆ P^{NP}, puis que coNP ⊆ NP/1 ⇒ P^{NP} ⊆ DP. Question 2 – Justifier que ces deux étapes permettent de conclure.

Nous commençons par la première étape, à savoir, nous allons montrer l’implication coNP ⊆ NP/1 ⇒ Σ_{2} ⊆ P^{NP}.

1La réciproque est vraie également mais nous ne nous en occuperons pas ici. Il s’agit d’un résultat de Buhrman, Chang et Fortnow, dans One bit of advice, 2002.

Question 3 – Par NP-complétude de SAT, on peut supposer que l’oracle dans P^{NP} est SAT. Montrer que l’on peut de plus supposer que la taille des requêtes à l’oracle SAT sur les entrées de taille n est toujours la même.

Question 4 – Montrer que si coNP ⊆ NP/1, alors Σ_{2} ⊆ NP/1.

Question 5 – Montrer qu’il existe des langages Σ_{2}-complets de la forme

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

où A ∈ P et où les quantifications portent sur des mots de taille polynomiale.

À partir de maintenant, L désigne un langage Σ_{2}-complet de la forme donnée à la question 5. Question 6 – À la question 4, nous avons montré que L ∈ NP/1 sous l’hypothèse coNP ⊆ NP/1. Montrer que dans P^{NP}, et si l’on connaît le bit du conseil, sur l’entrée x on peut trouver, s’il existe, le y′ maximum tel que (∀z)[(x, y′, z) ∈ A].

Question 7 – Montrer que sous l’hypothèse coNP ⊆ NP/1, on a L ∈ P^{NP}, et conclure la première étape.

On s’attache maintenant à la seconde étape, à savoir, nous allons montrer l’implication coNP ⊆ NP/1 ⇒ P^{NP} ⊆ DP. On admettra que le problème LexMaxSat suivant sur les formules booléennes ϕ est P^{NP}-complet :

LexMaxSat = {ϕ satisfaisable / le plus grand x tel que ϕ(x) = 1 se termine par 1}.

Question 8 – Sous l’hypothèse coNP ⊆ NP/1, construire une machine N non déterministe fonctionnant en temps polynomial, avec un bit de conseil, qui sur la formule booléenne ϕ retourne x_{max}, le plus grand x tel que ϕ(x) = 1. Plus précisément, lorsqu’on lui fournit le bon conseil, N a au moins un chemin acceptant ssi ϕ est satisfaisable ; et à la fin de tous ses chemins acceptants, x_{max} est inscrit sur le ruban de sortie de N. Si en revanche on lui fournit le mauvais bit de conseil, il peut y avoir plusieurs chemins acceptant ayant des mots différents sur le ruban de sortie. On demande de plus que la machine vérifie à la fin que ϕ(x_{max}) est vraie, où x_{max} est le mot sur le ruban de sortie à la fin du chemin en cours, et qu’elle rejette si ce n’est pas le cas. Ainsi, dans tous les cas notre machine ne peut avoir de chemin acceptant que si ϕ est satisfaisable (condition nécessaire mais pas suffisante si on donne le mauvais conseil).

S’il existe un chemin acceptant de N tel que le mot final sur le ruban de sortie est x, on dira que x est l’un des mots renvoyés. On note N(ϕ, 0) le calcul de N sur ϕ avec le conseil 0, et N(ϕ, 1) avec le conseil 1. On définit le langage A_{1} suivant :

A_{1} = {ϕ satisfaisable / N(ϕ, 0) ou N(ϕ, 1) renvoie un mot se terminant par 1}.

Le langage A_{2} est celui reconnu par la machine non déterministe N_{2} fonctionnant ainsi : sur l’entrée ϕ, N_{2} simule N(ϕ, 0) et N(ϕ, 1). Si tous les mots renvoyés sont les mêmes, ou si l’une des deux simulations rejette, alors N_{2} rejette ϕ. Sinon, il existe x_{0} renvoyé par N(ϕ, 0), et x_{1} par N(ϕ, 1), avec x_{0} ≠ x_{1}. Alors N_{2} accepte ϕ si et seulement si min(x_{0}, x_{1}) se termine par 1 et max(x_{0}, x_{1}) se termine par 0. Question 9 – Montrer que A_{1} et A_{2} sont dans NP. Montrer que LexMaxSat = A_{1} \ A_{2} et conclure.