12/04/2001 Exposé à l'IML 1

Fonctions booléennes complexes

Jean Francis MICHON

LIFARjean-francis.michon@univ-rouen.fr

12/04/2001 Exposé à l'IML 2

Les complexités• La notion de Machine de Turing permet de donner une

définition rigoureuse de la complexité.• On distingue ici 3 complexités d ’une fonction f:

– algorithmique (Chaitin-Kolmogorov) : taille du plus petit programme qui calcule f : CA(f)

– en temps : combien de temps pour calculer f(n) : CT(n) n étant la taille des données

– en espace: combien de mémoire nécessaire : CE(n) ?

• Ces complexités dépendent bien sûr du type de machine de Turing utilisé.

12/04/2001 Exposé à l'IML 3

Fonctions booléennes

• Définition : C ’est une application d ’un ensemble quelconque vers {0,1}.

Définition risquée : prendre un sous ensemble non récursif de N alors la fonction caractéristique de cet ensemble n ’est pas calculable! On se restreindra aux ensembles finis.

Pas de structure algébrique à priori mais plusieurs potentielles.

12/04/2001 Exposé à l'IML 4

Définition 2 : On appellera fonction booléenne à n variables toute application

f : {0,1}n {0,1} (n 0)

L ’étude des fonctions booléennes est donc équivalente à

l ’études des parties de {0,1}n

On note leur ensemble Bn

Card (Bn) = 22n

Pour installer une structure sur Bn il suffit d ’en mettre une

sur {0,1} et de « relever » la structure.

On a deux possibilités « classiques ».

12/04/2001 Exposé à l'IML 5

Structure 1 : {0,1} est une algèbre de Boole : on utilise deux opérations binaires , et une unaire

Structure 2 : {0,1} est un corps fini avec la loi + et

Attention le + correspond au XOR des informaticiens,le correspond au .

Remarque : On en déduit respectivement pour {0,1}n • une structure d ’algèbre de Boole .• une structure de F2 - algèbre (et pas de corps). Cette algèbre n’est autre que l’algèbre produit (F2 )n. Ne pas confondre cette algèbre avec le corps fini F2

n.

12/04/2001 Exposé à l'IML 6

Les structures induites sur Bn sont, respectivement

1/ : aussi une structure d ’algèbre de Boole (c ’est

l ’algèbre de Boole des parties de {0,1}n

exemple : f (x,y,z)(g(x,y,z) h(x,y,z))

2/ : une structure de F2-algèbre isomorphe à

F2[X1,…,Xn]/(X12+X1,…,Xn

2+Xn) F 2^n

exemple : 1+x+yz+xyz

Dans les deux cas les variables désignent les fonctions coordonnées sur Bn.

12/04/2001 Exposé à l'IML 7

Formes normales canoniques(uniques à l’ordre près des termes et des variables)

Forme normale disjonctive canonique (fndc)

exemple à 2 variables :

x y = (x y’ ) ( x y) (x’y) où y ’= yForme normale conjonctive canonique (fncc)

exemple à 2 variables : x y est une fncc.

Forme normale polynomiale (ordre degré-lexicographique):

exemple à 2 variables : x y = x+y+xy

12/04/2001 Exposé à l'IML 8

Les formes normales sont difficiles à utiliser dès que le nombre des variables est grand : elles comportent au plus

2n termes.

La fndc par exemple n’est autre que la table de vérité de la fonction f.La fncc n ’est autre que la table de vérité de sa fonction

complémentaire f=1+f (qu ’on note souvent f ’). Exemple : la fndc de la constante 1 comporte 2n termes.

12/04/2001 Exposé à l'IML 9

Il existe donc une différence très marquée entre les deux écritures d’une fonction booléenne. C’est-à-dire entre

l ’écriture en , , et l ’écriture polynomiale. La différence peut être exponentielle en nombre de termes.

Les règles de conversion d’une écriture vers l’autre sont les suivantes :

f g = f+g+fg f g = fg f = 1+f

f + g = (f g) ( f g)

12/04/2001 Exposé à l'IML 10

Pourquoi l ’étude des fonctions booléennes est elle difficile ? :

L ’existence des formes polynomiales montre que cette étude est équivalente à celle de la géométrie algébrique sur F2.

Tout ensemble de n-uples de bits est envisageable comme un ensemble de points rationnels sur F2 d ’une variété algébrique définie sur F2.

L ’exploration informatique est difficile : pour n>5, on ne peut plus faire de recherches exhaustives.

12/04/2001 Exposé à l'IML 11

Arbre de vérité

x=0 x=1

1 0

z

0 1

z

y

0 1

z

1 1

z

y

x

12/04/2001 Exposé à l'IML 12

La Table de vérité (ordre lexicographique)

x,y,z f(x,y,z)000 1001 0010 0011 1Etc..

Espace nécessaire pour le stockage 2n bits

12/04/2001 Exposé à l'IML 13

Pour toute fonction booléenne à n variables, son arbre de vérité comporte

2n-1 nœuds non terminaux

2n nœuds terminaux (feuilles)

2(2n-1) arcs

L ’arbre de vérité permet l ’interprétation de l ’identité de Boole (1854 : The Law of Thought) :

f(x,y,…)= x ’f(0,y,…) + x f(1,y,…)

qui s ’écrit aussi (remarquable)

f(x,y,…)= x ’f(0,y,…) xf(1,y,…)

ainsi

12/04/2001 Exposé à l'IML 14

f(0,y,z) f(1,y,z)

1 0

z

0 1

z

y

0 1

z

1 1

z

y

x

12/04/2001 Exposé à l'IML 15

Arbre de vérité = automate

z z

y

z z

y

x

1 0

Etat initial

Etat final

Etat puit

12/04/2001 Exposé à l'IML 16

1 (final)0

BDD quasi réduit = Automate minimal= Identification des sous-arbres isomorphes

12/04/2001 Exposé à l'IML 17

Réduction L ’identification des sous arbres isomorphes est toujours possible si n>3.

En effet le nombre des sous arbres de hauteur 1 dans l ’arbre de vérité est 2 n-1 , c ’est plus grand que le nombre de fonctions booléennes à 1 variable (qui est 4). Tous les sous arbres de hauteur 1 vont donc s ’identifier en au plus 4 classes.

De même pour les sous arbres de hauteur 2 qui vont se repartir en au plus 16 classes etc..

12/04/2001 Exposé à l'IML 18

1 0

BDD (réduction des liens doubles)

12/04/2001 Exposé à l'IML 19

BDD : réduction supplémentaire du BDDQRLes BDD (Binary Decision Diagram) de Lee (1959) et Ackers 1978, étudiés par R.E. Bryant (1986) sont issus d ’une étape supplémentaire de réduction à partir du BDDQR.

Si lors d ’une étape de résuction, un état X a le même fils droit et gauche on identifie cet état x avec son successeur. Mais...

A

X

B

DC

A

B

DC

devient

12/04/2001 Exposé à l'IML 20

BDD et rang des noeuds

Le BDD n’est plus l’automate minimal, il ne reconnaît plus le même langage !

Les BDD ne sont pas des graphes, on doit faire figurer la variable concernée par chaque état. Les nœuds ont des rangs.

Le nombre de nœuds du BDD d’une fonction booléenne n’est donc pas une mesure de sa complexité algorithmique.

12/04/2001 Exposé à l'IML 21

BDDQR et complexité algorithmique

Le nombre d ’états (de nœuds) du BDDQR donne directement un majorant de la complexité algorithmique du calcul de la fonction booléenne.

La complexité en temps est toujours majorée par le nombre de variables.

La table de transition de l’automate est la table de transition de la machine de Turing:Etat Caract lu Etat suivant Caract écrit Déplacement

Initial 0 A 0 1

Initial 1 B 0 1

A 0 C 0 1

A 1 D 0 1

B 0 D 0 1

B 1 E 0 1

etc...

12/04/2001 Exposé à l'IML 22

Tous les QRBDD minimaux pour n=3

Nbre de nœuds Nbre de fonctions booléennes

4 (minimum) 2 (constantes 0 et 1)5 2 (z et 1+z)6 127 728 1449 (maximum) 24 les fonctions « dures »

Total: 256 fonctions booléennes dans B3

12/04/2001 Exposé à l'IML 23

Graphes des fonctions dures pour n=3

10

4!=24 manières d ’établir les connexions en bas

12/04/2001 Exposé à l'IML 24

Tous les QRBDD minimaux pour n=4

Nombre de nœuds Nombre de fonctions booléennesdu QRBDD5 (minimum) 2 (constantes 0 et 1)6 2 (t et 1+t)7 128 729 57610 175211 1065612 2073613 (maximum) 31728 les fonctions « dures »Total 65536

12/04/2001 Exposé à l'IML 25

Graphes des fonctions dures pour n=4

10

31728 manières d ’établir les connexions entre les rangs 3 et 4 (flèches rouges) . Pourquoi?

12/04/2001 Exposé à l'IML 26

Fonctions booléennes dures

On peut chercher pour un nombre de variables donné, quelles sont les fonctions booléennes dont le BDDQR possède un nombre maximal de nœuds.

De telles fonctions booléennes seront dites dures.

Il est assez facile de déterminer cette complexité maximale (Champarnaud-Pin) et notre objectif est de décrire les QRBDD correspondants et de les dénombrer.

12/04/2001 Exposé à l'IML 27

Complexité algorithmique des fonctions booléennes dures

Pour un nombre de variable n fixé , on considère la fonction

dn(k)= inf(2k-1,22 n-k+1)

Alors

Cmax = Complexité algo maximale des fonction booléennes à n variables = dn(1)+…+dn(n+1)

n = 3 Cmax = 1+2+4+2 = 9

n = 4 Cmax = 1+2+4+4+2 = 13

n = 5 Cmax = 1+2+4+8+4+2 = 21

12/04/2001 Exposé à l'IML 28

Fonctions dures (suite)

Cmax = Complexité (nombre de nœuds) maximale = dn(1)+…+dn(n+1)

n = 3 Cmax = 1+2+4+2 = 9

n = 4 Cmax = 1+2+4+4+2 = 13

n = 5 Cmax = 1+2+4+8+4+2 = 21

n = 6 Cmax = 1 + 2 + 4 +8 +16 + 4 +2 = 37

n = 7 Cmax = 1 + 2 + 4 +8 +16 + 16 + 4 + 2 = 53

n = 8 Cmax = 1 + 2 + 4 +8 +16 + 32 +16 + 4 + 2 = 85

n= 9 Cmax = 1 + 2 + 4 +8 +16 + 32 + 64 +16 + 4 + 2 =149

12/04/2001 Exposé à l'IML 29

QRBDD des fonction dures

Arbre binaire

hauteur n - log2n

Une seule possibilité de connexion

Arbre comprimé

hauteur log2n

Une seule possibilité de connexion

Zone d ’Inflexion

12/04/2001 Exposé à l'IML 30

Dénombrement des possibilités n=3

Seul le rang 3 offre des possibilités de connexion variées : 4 types de connexions à répartir

sur 4 sommets : 4! = 24 possibilités.

C ’est la zone d ’inflexion

12/04/2001 Exposé à l'IML 31

Dénombrement : cas de n=4

L ’exploration par ordinateur montre que le nombre de configurations est 31728. On remarque d ’abord qu’une configuration étant donnée on peut la permuter de 4!=24 façons différentes: 31728=24 x 1322. Il y a donc 1322 configurations distinctes à permutation près.

12/04/2001 Exposé à l'IML 32

Dénombrement : cas généralOn note le nombre de configurations des flèches k!A(m,k)où m est le nombre de nœuds du rang inférieur et k le nombre de nœuds du rang supérieur (zone d ’inflexion). Chaque nœud du rang inférieur est indexé de 1 à m. Il y a toujours deux flèches qui sortent de chaque nœud supérieur, elles atteignent respectivement les nœuds i et j du rang inférieur (éventuellement i=j). Le couple (i,j) est unique par le principe de minimisation : sinon les nœuds dont elles sont issues seraient identifiés. D ’autre part tous les nœuds du rang inférieur reçoivent au moins une flèche.On peut donc poser le problème sous la forme combinatoire suivante :

12/04/2001 Exposé à l'IML 33

Problème combinatoireDans un carré m x m cocher k cases de

façon que, pour tout i (1 i m), la ligne i ou la colonne i contienne au moins une case cochée.

On appelle configuration correcte un tel ensemble de k cases.

Combien y a t il de configurations correctes ?Ce nombre n ’est autre que le A(m,k) précédent. Ci-contre, un exemple de configuration correcte, pour m=4 et k=4

12/04/2001 Exposé à l'IML 34

SolutionSi k > m2 alors A(m,k)=0 .

Si (m-1)2 < k m2 alors A(m,k) = m2

k

car toutes les configurations de k points sont correctes.

Dans les autres cas :

A(m,k)= - m A(m-1,k) - (m(m-1)/2) A(m-2,k) - ...m2

k

On retranche à l ’ensemble de toutes les configurations de k cases, celles qui ratent exactement un indice, puis celles qui en ratent exactement 2, etc...

12/04/2001 Exposé à l'IML 35

Pourquoi 31728 ?

Calculons A(4,4) :A(4,4) = (16.15.14.13/1.2.3.4) - 4A(3,4) - 6A(2,4)

= 1820 - 4A(3,4) - 6A(3,4) =9.8.7.6/1.2.3.4) - 3A(2,4)=126 - 3 = 123Donc A(4,4) =1820 - 4*123 - 6 = 1820 - 498 = 1322

Finalement 1322*4!=31728

12/04/2001 Exposé à l'IML 36

Forme expliciteJe ne connais pas de forme algébrique générale sympatique

des fonctions dures. On peut néanmoins donner leur table de vérité d ’après le

tableau combinatoire précédent .Par exemple en code hexadécimal la fonction de table de

vérité : 0123456789ABCDEF est dure !

C’est la table de vérité d’une fonction de 6 variables 26 = 16x4 =64 bits . En fait on peut montrer que, pour 6

variables, les tables de vérité des fonctions dures correspondent exactement aux 16! permutations des 16

symboles hexa.

12/04/2001 Exposé à l'IML 37

Classement des fonctions booléennes par leur complexité

La plus petite complexité est n + 1 (pour les 2 fonctions constantes 0 et 1). Comment se répartissent les fonctions booléennes entre n +1 et Cmax? On l’a vu pour n = 3 et n = 4. Il « semble » que les fonctions booléennes sont très souvent dures (une sur deux si n = 4).

L ’ estimation asymptotique de la proportion (densité)

n = nbre de fonctions dures pour n donné

22n= nbre de fonctions booléennes

semble difficile. Je pense que n tend vers 0 (lentement)

12/04/2001 Exposé à l'IML 38

RésultatsOn a obtenu les résultats suivants :

•La complexité des fonctions dures est invariante par un « gros sous groupe » de Sn. Pour certaines valeurs spéciales de n de la forme a+2a la complexité est

totalement invariante par Sn. •Le degré des fonctions dures tend vers l’infini avec n.

•Il existe des fonctions dures équilibrées c ’est-à-dire de poids de Hamming 2 n-1.

•La complexité maximale des BDD peut être déduite de celle des QRBDD. On obtient les fonctions « super dures »

12/04/2001 Exposé à l'IML 39

Questions ouvertes

Montrer que la densité des fonctions dures tend vers 0 avec le nombre des variables .

Plus généralement quel est le spectre de complexité des fonctions booléennes à n variables (voir les calculs

présentés pour n=3 et 4)Etude de la transformation de Fourier Walsh Hadamard des fonctions dures : certaines fonctions dures atteignent

elles la distance maximale aux fonctions affines?

12/04/2001 Exposé à l'IML 40

Applications

Classement de certaines fonctions connues (linéaires, addition binaire, multiplication, fonctions courbes, S-box du DES, etc…)

Les fonctions dures forment une catégorie dans laquelle on peut chercher des candidats pour des

problèmes ou des conjectures (crypto, codes).

Actuellement je les utilise comme candidates pour la recherche de fonctions à distance

maximale de R(1,m) .

12/04/2001 Exposé à l'IML 41

Le groupe symétrique

On peut faire agir le groupe Sn des permutations de n variables sur les fonctions booléennes . Si s est une permutation de Sn et f une fonction booléenne de Bn on pose :

fs (x1,…,xn) = f( xs(1),…,xs(n))

Cette opération est en faite une représentation linéaire de Sn sur l ’espace Bn : représentation de caractéristique 2 et de dimension 2n.

12/04/2001 Exposé à l'IML 42

Groupe symétrique et complexité

La complexité du QRBDD d’une fonction booléenne n’est pas invariante par l ’action des permutations.

On se pose les questions suivantes:

•Comment trouver une permutation qui minimise la complexité d’une fonction booléenne donnée ? Il semble que le problème soit NP complet (Bollig & Wegener)

•Comment se comportent les fonctions dures sous cette action ?

•Existe-t-il des fonctions -dures, c’est-à-dire dont toutes les permutées sont dures en dehors des valeurs spéciales?

12/04/2001 Exposé à l'IML 43

De Sn à S2n

Toute permutation est produit de transpositions. On montre facilement qu’on peut n’utiliser que des transposition du type (i i+1) , où 1i n-1. On appellera échange une telle transposition.

On peut étudier l’effet d’un échange sur un arbre binaire.

Plus généralement la permutation des variables induit une permutation sur les fonctions booléennes donc un homomorphisme de Sn vers S2

n. Lien avec les matrices de Sylvester et la transformation de Fourier-Hadamard.

12/04/2001 Exposé à l'IML 44

Echange de variables sur l ’arbre de vérité

xi+1

xi xi

A C B D

xi

xi+1 xi+1

A B C D

Les sous-arbres B et C sont échangés. De nouveaux sous-arbres enracinés en xi apparaissent mais pas de nouveaux sous-arbres plus bas, ni plus hauts.

12/04/2001 Exposé à l'IML 45

Exemple d ’effet d ’un échange

0 0 1 1 0 1 0 1

échange

0 1 0 1

réductionréduction

12/04/2001 Exposé à l'IML 46

Fonctions symétriques

Les fonctions symétriques booléennes jouent certainement un rôle dans la question du comportement de la complexité sous l’action du groupe des permutations.

Considérons la sous-algèbre des fonctions symétriques Bsym. L’algèbre Bn est alors une Bsym-algèbre et on connaît des générateurs (base ?). Quelle est la complexité de ces générateurs?

La complexité des BDD de fonctions symétriques a été calculée (Don Ross- thèse U. of Texas.)

12/04/2001 Exposé à l'IML 47

Bibliographie• Mon travail sur le sujet est mis à jour dans un document technique

« Fonctions booléennes » disponible sur demande. On y trouvera quelques exemples explicites, des démonstrations, ainsi que les nombreuses identités magiques que vérifient les A(m,k).

• Sur le problème de l ’ordre des variables et de son impact sur la complexité : Beate Bollig et Ingo Wegener Improving the variable ordering in OBDD is NP complete. IEEE Transactions on Computers Vol45 n°9 sept 1996.

12/04/2001 Exposé à l'IML 48

Bibliographie suite Beate Bollig et Ingo Wegener : Asymptotic optimal bounds for OBDDs ans the solution of some basic obdd problems ICALP 2000 LNCS 1853p.187-198

Les relations entre BDD et codage sont présentées dans : John Lafferty et Alexander Vardy Ordered Binary Decision Diagrams and Minimal treillises, IEEE Transactions on computers Vol 48 N°9 September 1999.

Une présentation claire sur les questions concernant les codes de Reed Muller se trouve dans la thèse de Caroline Fontaine (INRIA-Groupe codes )