Modèles de calcul, TD numéro 8

Natacha Portier jeudi 28 mars 2002

Une suite de circuits C = (C_{n})_{n∈N} est polynomiale uniforme s’il existe une machine de Turing travaillant en espace logarithmique qui sur l’entrée 1^{n} produit en sortie C_{n}.

Un langage est T UP S(f, g) s’il est reconnu par une suite de circuits polynomiale uniforme C telle que C_{n} soit de profondeur O(f(n)) et de taille O(g(n)).

La classe NC est l’union des classes T UP S(f, g) où f est une puissance du logarithme et g un polynôme. La classe NC_{i} est l’union des classes T UP S(f, g) où f = log^{i} et g est un polynôme.

Question 1

Montrer qu’un langage P est reconnu par une suite de circuits de taille polynomiale.

Question 2

Montrer qu’il existe un langage non décidable qui est reconnu par une suite de circuits de taille polynomiale.

Question 3

Montrer qu’il existe un langage qui n’est pas reconnu par une suite de circuits de taille polynomiale.

Question 4

Montrer qu’un langage est reconnu par une suite de circuits polynomiale uniforme si et seulement s’il est P.

Question 5

Le problème CHEM est celui d’accessibilité dans les graphes : étant donné un graphe orienté et deux de ses sommets s_{1} et s_{2}, y a-t-il un chemin de s_{1} à s_{2} dans le graphe ?

Question 5,1 Trouver une suite de circuits polynomiale uniforme pour CHEM en considérant un circuit dont les portes sont g_{i,j,k} avec 1 ≤ i, j ≤ n et 0 ≤ k ≤ n, et h_{i,j,k} avec 1 ≤ i, j, k ≤ n, où n est le nombre de sommets du graphe. Intuitivement, g_{i,j,k} vaut 1 s’il existe un chemin du sommet i au sommet j qui n’utilise pas de sommet intermédiaire (autre que i et j) plus grand que k, et h_{i,j,k} vaut 1 s’il existe un chemin du sommet i au sommet j qui n’utilise pas de sommet intermédiaire plus grand que k mais qui utilise k exactement une fois. Donner la taille et la profondeur du circuit. Question 5,2 Montrer que CHEM est T UP S(n, n^{3}). Question 5,3 Donner un circuit qui multiplie deux matrices carrées booléennes de taille n en temps séquentiel O(n^{3}) et temps parallèle O(1 + log n). Question 5,4 Montrer que CHEM est T UP S(log^{2} n, n^{3} log n). Question 6,1 Montrer que si L se réduit par une machine de Turing travaillant en espace logarithmique à un langage L′ dans NC alors L est dans NC. Question 6,2 Montrer que si L se réduit par une machine de Turing travaillant en espace logarithmique à un langage L′ dans NC_{j} et j ≥ 2 alors L est dans NC_{j}. Question 7,1 Montrer que pour tout entier i > 1 nous avons NC_{i} ⊆ DSP ACE(log^{i}). Question 7,2 Montrer que NC ≠ P SP ACE.