Modèles de calcul, TD numéro 5

Natacha Portier lundi 11 mars 2002

Question 1,1

Donner un circuit booléen qui calcule la somme de deux entiers y_{n}...y_{1} et x_{n}...x_{1} écrits en base 2 de taille n et évaluer sa taille et sa profondeur.

Question 1,2

On améliore la profondeur du circuit précédent de la manière suivante. On suppose que n est une puissance de 2. On calcule en parallèle la somme de y_{n/2}...y_{1} et x_{n/2}...x_{1} ainsi que les sommes y_{n}...y_{n/2+1}+x_{n}...x_{n/2} et y_{n}...y_{n/2+1}+ x_{n}...x_{n/2} + 1, puis on choisit le résultat en fonction de la retenue. Évaluer la taille et la profondeur du circuit.

Question 1,3

Généraliser la construction précédente (¡¡diviser pour régner¿¿), donner la taille et la profondeur du circuit obtenu.

Question 2

Montrer que si C est un circuit booléen dont aucune entrée n’est une sortie, alors :

t(C) ≤ 3(t(C) − e(C))

Question 3

Montrer que pour tout terme T, alors 2e(T) − 1 ≤ t(T), et il y a égalité si toutes les portes qui ne sont pas des entrées reçoivent deux flèches.

Question 4

Montrer que si T est un terme on peut trouver un terme T′ équivalent (donc en particulier avec le nombre d’entrées), de taille et de profondeur inférieure et qui satisfasse :

2e(T′) − 1 ≤ t(T′) ≤ 3e(T′) − 1

Question 5

Le nombre de portes d’un circuit C est une mesure pertinente de sa taille. En effet, on montrera que le nombre de flèches est compris entre t(C) − s(C) et 2(t(C) − e(C)).

Question 6

Montrer que pour tout circuit C :

p(C) ≤ t(C) − e(C) et t(C) ≤ s(C).(2^{p(C)+1} − 1)

. Montrer que pour tout terme T, log_{2}(e(T)) ≤ p(T).

Question 7

Théorème de Hoover, Klawe et Pippenger : À tout circuit booléen C correspond un circuit équivalent C^{∗} de degré sortant deux tel que

t(C^{∗}) ≤ 3t(C) et p(C^{∗}) ≤ 2p(C) + log_{2}(s(C))

. Question 7,1

Montrer le résultat pour la taille. Qu’obtient on pour la profondeur ?

Question 7,2

On introduit la notion de pondération dans un arbre binaire renversé. Si toute sortie (toute feuille) est affectée d’un poids, qui est un entier positif, on définit inductivement le poids d’un noeud de l’arbre comme étant le maximum des poids de ses fils, augmenté de un. Montrer que quelle que soit la distribution de poids entiers a_{1}, ..., a_{n} dont on affecte les points p_{1}, ..., p_{n}, il est possible de construire au dessus un arbre renversé dont le poids c de la racine satisfasse 2^{c} < 2.(2^{a_{1}} + ... + 2^{a_{n}}).

Question 7,3

Soit C un circuit. On le découpe en niveaux à partir du bas. Soit N_{0} l’ensemble des sorties et N_{1} l’ensemble des portes qui n’émettent des flèches que vers des sorties. L’ensemble N_{2} est constitué des portes qui n’émettent des flèches que vers des portes de N_{0} ou N_{1}. On veut que le circuit soit bien étagé, c’est-à-dire que les portes de N_{2} n’émettent des flèches que vers des portes de N_{1}. Pour cela, on ajoute éventuellement des portes d’identité au niveau N_{1} entre une porte de N_{2} et une sortie. On construit de même tous les niveaux du circuit. Donner un exemple de cette construction sur un circuit de votre choix.

Question 7,4

Utiliser les deux questions précédentes pour montrer le résultat sur la profondeur.

Question 8

Montrer que toute fonction booléenne en n variables peut être représentée par un terme booléen de profondeur (au plus) n + log_{2} n + 2 et de taille exponentielle en n. En déduire que pour tout polynôme p il existe pour n assez grand une fonction n-aire non exprimable par un terme de taille p(n). C’est l’effet Shannon. Il montre l’existence de problèmes non-polynomiaux.

Question 9

Montrer que tout circuit acceptant tous les 00..010..00 et refusant 00...0 a une profondeur supérieure ou égale à log_{2} n. En déduire que l’expression de la fonction Sup(x_{1}, ..., x_{n}) nécessite un circuit de profondeur au moins log_{2} n (et donc qu’il n’est pas raisonnable d’exiger des circuits de profondeur moins que logarithmique).

Question 10

Théorème de Spira : Tout terme booléen de taille t est équivalent à un terme de profondeur inférieure à 4 log_{2} t.

Le montrer par induction sur t, en extrayant un sous-terme minimal de taille strictement supérieure à t, puis en utilisant le sélecteur.

Question ouverte

P=NC ? C’est le problème du temps parallèle. Est-ce que les circuits sont vraiment plus puissants que les termes ? Est-il possible de transformer de manière polynomiale tout circuit en un terme équivalent ?