M1, 2005–2006

Complexité structurelle – TD 3 Langages creux et unaires

1 Une conséquence de Mahaney

Exercice 1 Montrer (sans utiliser le théorème de Mahaney) qu’il existe un langage creux NP-complet si et seulement s’il existe un langage creux NP-difficile.

2 Changement d’échelle

On rappelle les deux définitions suivantes :

E = ⋃_{c≥0} DTIME(2^{cn})

et

NE = ⋃_{c≥0} NTIME(2^{cn}).

Exercice 2 (Échauffement gentil avant l’exercice 3) Montrer que si E = NE alors tous les langages unaires de NP sont dans P.

Exercice 3 Montrer que les trois assertions suivantes sont équivalentes :

(i) E = NE ; (ii) NP − P ne contient pas de langage creux ; (iii) NP − P ne contient pas de langage unaire. On pourra montrer (iii)⇒(i) (réciproque de l’exercice 2), puis (i)⇒(ii), puis conclure.

3 Une autre caractérisation de P/poly

Exercice 4 Montrer que

P/poly = ⋃_{S creux} P^{S} = ⋃_{T unaire} P^{T} .

En déduire que s’il existe un langage creux NP-difficile pour les réductions Turing, alors il existe un langage unaire NP-difficile pour les réductions Turing.