Partiel de modèles de calcul et complexité Natacha Portier le 16 avril 2002

Notes de cours et de TD autorisées Rédaction soignée indispensable !

Problèmes avec fonction de sélection polynomiale

Définition : un problème X est dans P − sel (pour P sélectif) s’il existe une fonction de {0; 1}^{∗} × {0; 1}^{∗} dans {0; 1}^{∗} calculable en temps polynomial telle que pour tout (x, y) ∈ {0; 1}^{∗} × {0; 1}^{∗} on ait f(x, y) ∈ {x, y} et {x, y} ∩ X ≠ ∅ ⇒ f(x, y) ∈ X. On dit alors que f est une fonction de sélection pour X.

Question 1

Montrer que P ⊆ P − sel.

Question 2,1

Soit r un réel. Soit X l’ensemble des uples b_{1}...b_{n} d’éléments de {0; 1} tels que n soit un entier et 0, b_{1}...b_{n} ≤ r. Montrer que X est P − sel.

Question 2,2

Montrer qu’il existe un problème P − sel mais non récursif.

Question 3

Soit (M_{1}, p_{1}), (M_{2}, p_{2}), … une énumération récursive de tous les couples (M, p) tels que p(X) soit un polynôme (de la forme X^{k}) et M une machine de Turing qui pour tout entier n et toute entrée de taille n effectue au plus p(n) pas de calcul. Soit (w_{i}) une suite d’entiers définie par : w_{0} = 2 et pour tout n entier naturel w_{2n+1} = 1 + w_{2n} et w_{2n+2} = 2^{2^{2^{w_{2n}}}}. Définissons le langage L de la manière suivante. Pour tous les entiers i et m, si M_{i}(w_{2<i,m>}, w_{2<i,m>+1}) = w_{2<i,m>} alors w_{2<i,m>+1} ∈ L, si M_{i}(w_{2<i,m>}, w_{2<i,m>+1}) = w_{2<i,m>+1} alors w_{2<i,m>} ∈ L, et L ne contient rien d’autre. Remarque : < i, m > est le code habituel du couple (i, m) (dont on pourra préciser les bonnes propriétés). On peut supposer que l’alphabet d’entrée des machines considérées contient 0, 1 et la virgule.

Montrer que L est récursif sans être dans P − sel.

Question 4

Montrer que si X est P − sel alors son complémentaire l’est aussi.

Question 5

Nous allons montrer que P − sel ⊆ P/poly. On donne les définitions suivantes : Soit C une classe de complexité et F un ensemble de fonctions de N dans N. La classe C/F est l’ensemble des problèmes X tels qu’il existe un problème Y dans C, une fonction f dans F, une suite (a_{n}) de uples de booléens telle que pour tout entier n le uple a_{n} (appelé conseil pour les mots de longueur n) soit de longueur au plus f(n), et vérifiant : pour tout n-uple x de booléens, x ∈ X si et seulement si (a_{n}, x) ∈ Y. Soit lin l’ensemble des fonctions linéaires de N dans N, quad l’ensemble des polynômes de degré au plus deux de N dans N et poly l’ensemble des polynômes de N dans N.

Question 5,1

Définition : Un tournoi est un graphe complet fini dont on oriente les arêtes (de manière quelconque). Imaginez par exemple un ensemble de n joueurs et tous les matches où deux joueurs s’affrontent. Les sommets du tournoi sont alors les joueurs et chaque arête pointe vers le gagnant du match (on n’admet pas de match nul).

Lemme : Si G est un tournoi dont l’ensemble des sommets est V_{G} = {1; 2; …; k} et l’ensemble des arêtes est E_{G} alors il existe un sous-ensemble H des sommets de cardinal au plus ⌊log(k + 1)⌋ tel que pour tout v ∈ V_{G} − H il existe g ∈ H tel que (v, g) ∈ E_{G}. (le log est en base 2)

Prouver le lemme, par exemple par récurrence.

Question 5,2

Soit X dans P − sel. Montrer qu’il existe une fonction de sélection f pour X telle que pour tout x et y, f(x, y) = f(y, x).

Question 5,3

Soit X dans P − sel et soit une fonction de sélection f pour X telle que pour tout x et y, f(x, y) = f(y, x). Considérons l’ensemble X^{=n} des mots de X de longueur n.

Montrer qu’il existe un sous-ensemble H_{n} de X^{=n} de cardinal au plus n + 1 tel que pour tout mot v de longueur n, v appartient à X^{=n} si et seulement s’il existe un mot g de H_{n} tel que f(v, g) = v.

Question 5,4

Conclure.

Question 5,5 Montrer que P − sel ⊆ P/quad. Question 6 Nous allons montrer que P − sel ⊆ NP/lin. Question 6,1 Lemme : Si G est un tournoi alors il existe un sommet s tel que tout sommet soit accessible à partir de s par un chemin orienté de longueur au plus deux.

Montrer ce lemme (par exemple par récurrence). Question 6,2 Montrer que P −sel ⊆ NP/lin. Si X est dans P −sel et f est une fonction de sélection bien choisie pour X, on pourra considérer pour tout entier n le tournoi dont l’ensemble des sommets est X^{=n} et les arêtes les (x, y) tels que f(x, y) = y. Question 6,3 Montrer que P − sel ⊆ NP/lin ∩ coNP/lin Question 6,4 Montrer que P − sel ⊆ NP/n + 1 (NP/n + 1 = NP/{f : n ↦ n + 1}). Question 7 Nous allons montrer que P − sel ⊈ NP/n (NP/n = NP/{f : n ↦ n}).

Soit l_{0} = 2 et pour tout entier i strictement positif l_{i} = 2^{2^{2^{l_{i−1}}}} . Soit E l’ensemble des l_{i}. L’ensemble des mots booléens est muni de l’ordre lexicographique et on utilisera les notations habituelles ≤, min, ... Si X est un ensemble de mots booléens considérons les conditions suivantes :

(1) Pour tout mot x de X la longueur de x est dans E.

(2) Pour tous x et y de même longueur, x ≤ y et y ∈ X implique x ∈ X.

(3) X ∈ DT IME[2^{2^{n}}] Question 7,1 Montrer que si X satisfait les conditions (1), (2) et (3) alors X est P − sel. Pour cela on peut considérer la fonction suivante :

f(x, y) = \begin{cases}x & si|y| ∉ E \\ y & si|y| ∈ E ∧ |x| ∉ E \\ min\{x, y\} & si|y| ∈ E ∧ |x| ∈ E ∧ |x| = |y| \\ min\{x, y\} & si|y| ∈ E ∧ |x| ∈ E ∧ |x| ≠ |y| ∧ min\{x, y\} ∈ X \\ max\{x, y\} & si|y| ∈ E ∧ |x| ∈ E ∧ |x| ≠ |y| ∧ min\{x, y\} ∉ X \end{cases}

Question 7,2

Soit N_{1}, N_{2} … une énumération (que l’on choisira bien) des machines de Turing non déterministes travaillant en temps polynomial, et soit N′_{1}, N′_{2} … l’énumération telle que pour tout k on ait N′_{<i,k>} = N_{i}. On définit le problème X de la manière suivante. Pour chaque entier l voici la définition de X^{=l}. Si l ∉ E alors X^{=l} = ∅. Sinon on effectue le calcul suivant, et si celui-ci nécessite plus de 2^{2^{l}} pas de calcul alors on arrête le calcul et on pose X^{=l} = ∅. Soient i et k tels que l soit le < i, k >-ème élément de E. Pour chaque mot y de longueur l calculer le mot plusadroite(y) de la manière suivante. Pour chaque mot x de longueur l calculer N′_{<i,k>}(< x, y >). Si aucun de ces calculs n’accepte alors plusadroite(y) = 1^{l−1}. Sinon plusadroite(y) est le plus grand x de longueur l tel que N′_{<i,k>}(< x, y >) accepte. Soit J_{l} = ({0; 1}^{l} ∪ {1^{l−1}}) − {plusadroite(y)|y ∈ {0; 1}^{l}}, j_{l} = min(J_{l}) et X^{=l} = {x/|x| = l ∧ x ≤ j_{l}}. Montrer que J_{l} n’est pas vide (l ∈ E). Montrer que X ainsi défini est P − sel.

Question 7,3

Supposons que X soit NP/n grâce à la machine N_{I} et à la suite de mots (a_{j}). Montrer qu’il existe L ∈ E tel que le calcul de X^{=L} (cf ce qui précède) nécessite moins de 2^{2^{L}} pas de calcul et donc se termine sans être interrompu. Montrer qu’alors aucun mot a_{L} ne convient. Conclure

Question 7,4 (plus dure !)

Soit h une fonction récursive quelconque. Montrer que P − sel ⊈ DT IME[h(n)]/n