Réseaux de preuves booléens sous-logarithmiques · Réseaux de preuves booléens sous-logarithmiques Mémoire en vue de l’obtention du M2 L.M.F.I. à l’Université Paris VII

Réseaux de preuves booléenssous-logarithmiques

Mémoire en vue de l’obtention du M2 L.M.F.I.à l’Université Paris VII

Encadrants :V. Mogbil (L.I.P.N. - Université Paris XIII)P. Jacobé de Naurois (L.I.P.N. - C.N.R.S.)

Clément Aubert

Institut Galilée - Université Paris-Nord99, avenue Jean-Baptiste Clément

93430 Villetaneuse

23 septembre 2010

Deux modèles du calcul parallèle

Circuits booléens Réseaux de preuves

Correspondance ?

Problème : linéarise le temps de calcul.• Profondeur• Taille

• Uniformité• Ressources allouées à la transformation



Correspondance ?

Évaluation parallèle Élimination des coupures






Machine de Turing






Machine de Turing

Problème : linéarise le temps de calcul.

• Profondeur• Taille



Circuits booléens Réseaux de preuvesbooléens

Évaluation parallèle Élimination des coupuresTraduction

Simulation






Simulation


• Profondeur• Taille





Simulation


• Profondeur• Taille• Uniformité

• Ressources allouées à la transformation




Simulation


• Profondeur• Taille• Uniformité• Ressources allouées à la transformation

Tableau de correspondance

Circuits booléens Réseaux booléensEntrées Valeurs booléennes Réseaux de preuve de

type booléen

0 et 1

⊗`

•• ⊗

`

• •

Profondeur Chemin maximal Formule de coupureTaille Nombre de nœuds Nombre de liensCalcul Évaluation parallèle Élimination des coupures

Traduction

Simulation



type booléen

0 et 1

⊗`

•• ⊗

`

• •


Traduction

Simulation



type booléen

0 et 1

⊗`

•• ⊗

`

• •

Profondeur Chemin maximal Formule de coupure

Taille Nombre de nœuds Nombre de liensCalcul Évaluation parallèle Élimination des coupures

Traduction

Simulation



type booléen

0 et 1

⊗`

•• ⊗

`

• •

Profondeur Chemin maximal Formule de coupureTaille Nombre de nœuds Nombre de liens

Calcul Évaluation parallèle Élimination des coupures

Traduction

Simulation



type booléen

0 et 1

⊗`

•• ⊗

`

• •


Traduction

Simulation



type booléen

0 et 1

⊗`

•• ⊗

`

• •


Traduction

Simulation

1 Circuits booléens

2 Réseaux booléens

3 Exemples et composition

4 Circuits de preuve

5 Simulation

6 Résultats

Circuits booléens, familles de circuits

Exemples (Circuits booléens)

Définition (Uniformité)Une famille de circuits C = (Cn)n∈N est uniforme s’il existe unemachine de Turing déterministe qui étant donné n et le nom du nœudg peut déterminer toutes les informations sur le nœud g de Cn.



Définition (Bases)B0 = {¬,∧2,∨2

}

B1 = {¬, (∧n)n>2, (∨n)n>2}.




0 x1 x2

∧2 ¬

∨2

∧2


}

B1 = {¬, (∧n)n>2, (∨n)n>2}.




0 x1 x2

∧2 ¬

∨2

∧2

1 0 x1 x2

∧3 ¬

∨3


}

B1 = {¬, (∧n)n>2, (∨n)n>2}.




0 x1 x2

∧2 ¬

∨2

∧2

1 0 x1 x2

∧3 ¬

∨3


Classes de complexité

Définition (NC i (resp. AC i))Pour i ∈N, ensemble des fonctions booléennes calculables parfamilles de circuits booléens uniformes, où pour chaque circuit ayantn entrées,• sa profondeur est bornée par O(logi n),• sa taille est polynomiale en n,• ses nœuds sont étiquetés par des fonctions de B0 (resp. B1).

NC =⋃i∈N

NC i et AC =⋃i∈N

AC i .

ThéorèmePour tout k > 0, NCk

⊆ ACk⊆ NCk+1.

AC0 ( NC1⊆ L ⊆ NL ⊆ AC1

AC0(UstCONN2) ⊆ AC1



NC =⋃i∈N


AC i .

Définition (UstCONN2)Étant donnés le codage d’un graphe non-dirigé de degré 2 et lesnuméros de deux sommets, cette fonction détermine s’il existe unchemin entre ces deux sommets.

UstCONN2 ∈ L


⊆ ACk⊆ NCk+1.

AC0 ( NC1⊆ L ⊆ NL ⊆ AC1




NC =⋃i∈N


AC i .

Définition (UstCONN2)Étant donnés le codage d’un graphe non-dirigé de degré 2 et lesnuméros de deux sommets, cette fonction détermine s’il existe unchemin entre ces deux sommets.UstCONN2 ∈ L


⊆ ACk⊆ NCk+1.

AC0 ( NC1⊆ L ⊆ NL ⊆ AC1




NC =⋃i∈N


AC i .


⊆ ACk⊆ NCk+1.

AC0 ( NC1⊆ L ⊆ NL ⊆ AC1


Principaux résultats

Théorème ([Terui, 2004] )Pour tout circuit booléen C de taille |C | et de profondeur p(C) sur labase B1(UstCONN2), il existe un réseau de preuve booléen de tailleO(|C |4) et de profondeur O(p(C)) qui accepte le même ensemble.

Théorème ()Pour tout i ∈N, la traduction d’une famille de circuits booléensappartenant à AC i(UstCONN2) vers une famille de réseaux booléensde mBNi est dans L .



Problèmes :1 UstCONN2 ∈ L

2 Concernant B0 ?




Problèmes :1 UstCONN2 ∈ L2 Concernant B0 ?



Théorème ( [Aubert, 2010])Pour tout circuit booléen C de taille |C | et de profondeur p(C) sur labase B0 (resp. B1), il existe un réseau de preuve booléen de tailleO(|C |) (resp. O(|C2

|)) et de profondeur O(p(C)) qui accepte le mêmeensemble.





Théorème ([Mogbil et Rahli, 2007])Pour tout i ∈N, la traduction d’une famille de circuits booléensappartenant à AC i(UstCONN2) vers une famille de réseaux booléensde mBNi est dans L .




Théorème ([Aubert, 2010])Pour tout i ∈N, la traduction d’une famille de circuits booléensappartenant à AC i ou NC i vers une famille de réseaux booléens deCCP i est dans AC0 .





5 Simulation

6 Résultats

Règles de MLLu

Définition (Les règles de MLLu)ax .

` A ,A⊥` Γ1,A1 . . . ` Γn,An

⊗n

` Γ1, . . . , Γn,⊗n(A1, . . . ,An)

` Γ,A ` ∆,A⊥cut

` Γ,∆` Γ,An, . . . ,A1 `n` Γ,`n(An, . . . ,A1)

⊗`

••

⊗`

• •

Règles de MLLu


` A ,A⊥` Γ1,A1 . . . ` Γn,An

⊗n

` Γ1, . . . , Γn,⊗n(A1, . . . ,An)


` Γ,∆` Γ,An, . . . ,A1 `n` Γ,`n(An, . . . ,A1)

Définition (Le type booléen, [Terui, 2004])Le type booléen B est défini comme étant `3(α⊥, α⊥, α ⊗ α).

ax .` α⊥, α

ax .` α⊥, α

⊗2

` α⊥, α⊥, α ⊗ α`3

` `3(α⊥, α⊥, α ⊗ α)

⊗`

••

⊗`

• •

Règles de MLLu


` A ,A⊥` Γ1,A1 . . . ` Γn,An

⊗n

` Γ1, . . . , Γn,⊗n(A1, . . . ,An)


` Γ,∆` Γ,An, . . . ,A1 `n` Γ,`n(An, . . . ,A1)

ax .` α⊥, α

ax .` α⊥, α

⊗2

` α⊥, α⊥, α ⊗ α`3

` `3(α⊥, α⊥, α ⊗ α)

⊗`

•• ⊗

`

• •

Règles de MLLu


` A ,A⊥` Γ1,A1 . . . ` Γn,An

⊗n

` Γ1, . . . , Γn,⊗n(A1, . . . ,An)


` Γ,∆` Γ,An, . . . ,A1 `n` Γ,`n(An, . . . ,A1)

ax .` p : α⊥,p : α B axp

ax .` q : α⊥,q : α B axq

⊗2

` p : α⊥,q : α⊥, r : α ⊗ α B tenseurp,qr (axp ,axq)

`3` s : `3(α⊥, α⊥, α ⊗ α) B parq,p,r

s (tenseurp,qr (axp ,axq))

⊗`

•• ⊗

`

• •

Règles

Typage Réseau

ax .`

p :

A ,

p :

A⊥

. axp

•

p p

` Γ1,

p1 :

A1

. P1

. . . ` Γn,

pn

: An

. Pn

⊗n

` Γ1, . . . , Γn,

s :

⊗n (A1, . . . ,An)

. tenseur−→ps (−→P )

. . .Γ1

p1⊗. . .

. . .Γn

pn

s

` Γ,

pn :

An, . . . ,

p1 :

A1

. P

`n

` Γ,

s :

`n (An, . . . ,A1)

. parpn ,...,p1s (P)

. . .Γ

pn p1

`s

` Γ,

p :

A

. P

` ∆,

q :

A⊥

.Q

cut` Γ,∆

. cutp,q(P,Q). . .Γ

p . . .∆

q

Règles

Typage Réseau

ax .` p : A ,p : A⊥ . axp

•

p p

` Γ1,

p1 :

A1

. P1

. . . ` Γn,

pn

: An

. Pn

⊗n

` Γ1, . . . , Γn,

s :

⊗n (A1, . . . ,An)

. tenseur−→ps (−→P )

. . .Γ1

p1⊗. . .

. . .Γn

pn

s

` Γ,

pn :

An, . . . ,

p1 :

A1

. P

`n

` Γ,

s :

`n (An, . . . ,A1)


. . .Γ

pn p1

`s

` Γ,

p :

A

. P

` ∆,

q :

A⊥

.Q

cut` Γ,∆


p . . .∆

q

Règles

Typage Réseau

ax .` p : A ,p : A⊥ . axp

•

p p

` Γ1,p1 : A1 . P1 . . . ` Γn,pn : An . Pn⊗

n

` Γ1, . . . , Γn, s : ⊗n (A1, . . . ,An) . tenseur−→ps (−→P )

. . .Γ1

p1⊗. . .

. . .Γn

pn

s

` Γ,

pn :

An, . . . ,

p1 :

A1

. P

`n

` Γ,

s :

`n (An, . . . ,A1)


. . .Γ

pn p1

`s

` Γ,

p :

A

. P

` ∆,

q :

A⊥

.Q

cut` Γ,∆


p . . .∆

q

Règles

Typage Réseau

ax .` p : A ,p : A⊥ . axp

•

p p

` Γ1,p1 : A1 . P1 . . . ` Γn,pn : An . Pn⊗

n


. . .Γ1

p1⊗. . .

. . .Γn

pn

s

` Γ,pn : An, . . . ,p1 : A1 . P`n

` Γ, s : `n (An, . . . ,A1) . parpn ,...,p1s (P)

. . .Γ

pn p1

`s

` Γ,

p :

A

. P

` ∆,

q :

A⊥

.Q

cut` Γ,∆


p . . .∆

q

Règles

Typage Réseau

ax .` p : A ,p : A⊥ . axp

•

p p

` Γ1,p1 : A1 . P1 . . . ` Γn,pn : An . Pn⊗

n


. . .Γ1

p1⊗. . .

. . .Γn

pn

s

` Γ,pn : An, . . . ,p1 : A1 . P`n

` Γ, s : `n (An, . . . ,A1) . parpn ,...,p1s (P)

. . .Γ

pn p1

`s

` Γ,p : A . P ` ∆,q : A⊥ .Qcut

` Γ,∆ . cutp,q(P,Q). . .Γ

p . . .∆

q

Réseaux booléens

Définition (Réseau de preuve booléen, [Terui, 2004])Un réseau de preuve booléen à n entrées est un réseau de preuveP(−→p ) de type

` p1 : B⊥[A1], . . . ,pn : B⊥[An], s : ⊗1+m(B[A ],C1, . . . ,Cm)

Définition

. . .b0

b1

b0

b1. . . ⊗. . .

Réseaux booléens



Définition (→m et→a)Soit ◦ ∈ {•, (`n)n>2, (⊗n)n>2}.

`⊗. . . . . . . . . . . .

→m

. . . . . . . . . . . .

•→a

Définition

. . .b0

b1

b0

b1. . . ⊗. . .

Réseaux booléens



Définition

−→b ≡ . . .

b0

b1

b0

b1P(−→p ) ≡

. . . ⊗. . .

Réseaux booléens



Définition

. . .b0

b1

b0

b1. . . ⊗. . .

P(−→b ) ≡

Réseaux booléens



Définition

. . .b0

b1

b0

b1. . . ⊗. . .

P(−→b ) ≡

∗

⊗b0

b1

. . .





5 Simulation

6 Résultats

Un premier exemple : la négation

⊗`

••

•

•

•

⊗`


⊗`

••

•

•

•

⊗`


⊗`

••

•

•

•

⊗`

→m•• ⊗

`

•

•

•


⊗`

••

•

•

•

⊗`

→m•• ⊗

`

•

•

•


⊗`

••

•

•

•

⊗`

→m•• ⊗

`

•

•

•

↓a

•• ⊗

`


⊗`

••

•

•

•

⊗`

→m•• ⊗

`

•

•

•

↓a

•• ⊗

`

≡⊗

`

• •


⊗`

••

•

•

•

⊗`

→m•• ⊗

`

•

•

•

↓a

•• ⊗

`

≡⊗

`

• •

↓ev

Second exemple : le conditionnel

⊗`

• •

⊗•

⊗`•• ⊗

`

• •

→m

⊗`•• ⊗

`

• •

⊗• ••

→a ⊗⊗

`••⊗

`

• •

Nécessite de composer :

P

`

Q

•

•

...

`⊗••

•...


⊗`

• •

⊗•

⊗`•• ⊗

`

• •

→m

⊗`•• ⊗

`

• •

⊗• ••

→a ⊗⊗

`••⊗

`

• •


P

`

Q

•

•

...

`⊗••

•...


⊗`

• •

⊗•

⊗`•• ⊗

`

• •

→m

⊗`•• ⊗

`

• •

⊗• ••

→a ⊗⊗

`••⊗

`

• •


P

`

Q

•

•

...

`⊗••

•...


⊗`

• •

⊗•

⊗`•• ⊗

`

• •

→m

⊗`•• ⊗

`

• •

⊗• ••

→a ⊗⊗

`••⊗

`

• •


P

`

Q

•

•

...

`⊗••

•...


⊗`

• •

⊗•

⊗`•• ⊗

`

• •

→m

⊗`•• ⊗

`

• •

⊗• ••

→a ⊗⊗

`••⊗

`

• •


P

`

Q

•

•

...

`⊗••

•...

Un exemple de simulation

x1 x2 x3 x4

∨4

Simulation de [Terui, 2004]

`•

•b1

⊗•e1

•

e2 ⊗b1

•

e3

`

•

•

⊗`•

••

⊗b1

•

e4

`

•• ⊗

Un exemple de simulation

x1 x2 x3 x4

∨4

Simulation de [Aubert, 2010]

⊗

`•

•b1

⊗•e1

•

e2 ⊗b1

•

e3

`

•

•

⊗b1

•

e4

`

•

•





5 Simulation

6 Résultats

Pièces de circuits de preuves

b0 ≡

⊗`

••

s

b1 ≡

⊗`

• •

s

DUPL1≡

e

⊗•b0 b1

`

•

• s

g

NEG ≡

•

•

•

⊗`

e s


On pose 2 6 j 6 i.

DUPL i≡

⊗•⊗ ⊗

e

b0 b0

i fois︷︸︸︷b1 b1

i fois︷︸︸︷. . . . . . . . . . . .

`

•

`

•

g

...

••

•

• s1s2

si

si−1


On pose 2 6 j 6 i.

DISJ i≡

`•

•

g1b1

⊗•e1

•

e2

⊗b1

•

ej

`

•

gj−1

•

⊗b1

•

ei

`•

•

gi−1

s

i − 3 fois


On pose 2 6 j 6 i.

CONJ i≡

⊗`

e1•b0

•

g1

•

e2

•

⊗b0

•

ej

`

•

gj−1

•

⊗b0

•

ei

`•

•

gi−1

s

i − 3 fois

Composition de pièces et de circuits de preuves

Définition (Circuit de preuve)1 On compose des pièces (identifie une sortie d’une pièce avec

une entrée d’une autre pièce), sans boucler,2 on étiquette les entrées des pièces restées libres,3 on ajoute un tenseur conclusion qui collecte la sortie de la

dernière pièce et les poubelles générées.

Théorème ([Aubert, 2010])Tout circuit de preuve est un réseau de preuve booléen de MLLu.

Lemme (Traduction)Il est possible d’associer à tout circuit booléen Cn un circuit de preuveT (Cn) tel que si Cn s’évalue en i, T (Cn)→ev bi .





Définition (Composition de circuits de preuves)Soient C1 et C2 deux circuits de preuves. On les représente ainsi :

pièces de Ci

. . .entrées

sortie⊗poubelles

...







Définition (Composition de circuits de preuves)

pièces de C2

. . . . . .

⊗...

pièces de C1

. . ....















Principaux théorèmes

Soient Cn un circuit booléen, p(Cn) sa profondeur, |Cn | sa taille, et T (Cn) sontraduit en circuit de preuve, de profondeur d(T (Cn)) et de taille |T (Cn)|.

Théorème (Profondeur de T (Cn), [Aubert, 2010])d(T (Cn)) = O(p(Cn)).

Théorème (Taille de T (Cn), [Aubert, 2010])Si Cn appartient à une famille de circuits booléens comprise dans NC i (resp.AC i), |T (Cn)| = O(|Cn |) (resp. |T (Cn)| = O(|Cn |

2)).

Démonstration• Soit k le nombre d’arrêtes de Cn, k 6 2 × |Cn | (resp. k 6 |Cn |

2),

• un nœud de Cn d’arité entrante n et sortante m est représenté par unréseau de preuve de taille au plus 9(n + m),

• la somme des arités entrantes et sortantes de l’ensemble des nœuds deCn ne peut dépasser k .

Principaux théorèmesSoient Cn un circuit booléen, p(Cn) sa profondeur, |Cn | sa taille, et T (Cn) sontraduit en circuit de preuve, de profondeur d(T (Cn)) et de taille |T (Cn)|.


LemmeSoit P une pièce d’un circuit de preuve à n > 1 entrées et m > 1 sorties.Soient As1 , . . . ,Asm les formules à sa sortie et Ae1 , . . . ,Aen les formules à sonentrée. On a pour j ∈ {1, . . . ,n}

d(Aej ) 6 d(B) + max(d(As1), . . . ,d(Asm ))


2)).


2),



Principaux théorèmesSoient Cn un circuit booléen, p(Cn) sa profondeur, |Cn | sa taille, et T (Cn) sontraduit en circuit de preuve, de profondeur d(T (Cn)) et de taille |T (Cn)|.


LemmeSoit P une pièce d’un circuit de preuve à n > 1 entrées et m > 1 sorties.Soient As1 , . . . ,Asm les formules à sa sortie et Ae1 , . . . ,Aen les formules à sonentrée. On a pour j ∈ {1, . . . ,n}

d(Aej ) 6 d(B) + max(d(As1), . . . ,d(Asm ))

Démonstration• Soit xi l’entrée de T (Cn) où la formule de coupure est la plus profonde,

• le chemin de la sortie à xi passe par au plus p(Cn) × 2 pièces,

• on a donc d(T (Cn)) 6 p(Cn) × 2 × d(B).


2)).


2),







2)).


2),







2)).


2),







5 Simulation

6 Résultats

Définition (t-réduction)• •

DémonstrationC est composé de cinq sous-circuits :

1 transforme le code de P en fonction des entrées,2 simule les→t -réduction en parallèle,3 simule les→a-réduction en parallèle,4 simule les→m-réduction en parallèle,5 identifie si le résultat de l’évaluation est b0 ou b1.




Définition (t-réduction)•




. . .

•




. . .

•

→t

•




. . .

•

→t

•

Définition (⇒)On écrit P ⇒ Q si Q peut être obtenu depuis P en éliminant toutesles a-, m- ou t- coupures en parallèle.




. . .

•

→t

•

Définition (⇒)On écrit P ⇒ Q si Q peut être obtenu depuis P en éliminant toutesles a-, m- ou t- coupures en parallèle.

Théorème ([Terui, 2004])Il existe une séquence de réductions parallèles

P ⇒ P1 ⇒ . . .⇒ Pn

telle que Pn est sans coupures et n 6 3 × d(P).




. . .

•

→t

•

Théorème ([Terui, 2004])Pour tout réseau de preuve P de taille |P | et de profondeur d(P), ilexiste un circuit booléen C de taille O(|P |4) et de profondeur O(d(P))sur la base B1(UstCONN2) qui accepte le même ensemble que P.




. . .

•

→t

•

Théorème ([Terui, 2004])Pour tout réseau de preuve P de taille |P | et de profondeur d(P), ilexiste un circuit booléen C de taille O(|P |4) et de profondeur O(d(P))sur la base B1(UstCONN2) qui accepte le même ensemble que P.







5 Simulation

6 Résultats



NC =⋃i∈N


AC i


Définition (APN i, [Terui, 2004] (resp.mBN i,[Mogbil et Rahli, 2007]))Pour i ∈N, ensemble des fonctions booléennes calculables parfamilles de réseaux booléens non-uniformes (resp.uniformes), oùpour chaque circuit ayant n entrées,• sa profondeur est bornée par O(logi n),• sa taille est polynomiale en n.

APN =⋃i∈N

APNi (resp. mBN =⋃i∈N

mBNi)


Définition (CCP i [Aubert, 2010])Pour i ∈N, ensemble des fonctions booléennes calculables parfamilles de circuits de preuves uniformes, où pour chaque circuitayant n entrées,• sa profondeur est bornée par O(logi n),• sa taille est polynomiale en n.

CCP =⋃i∈N

CCP i

Le problème traduction

Définition (Traduction de AC i vers CCP i)On pose le problème suivant :

Entrée : Une description d’une famille de circuits booléensappartenant à AC i .

Sortie : Une description d’une famille de circuits de preuvesappartenant à CCP i tels que le résultat de l’évalua-tion via élimination des coupures de chaque circuitde preuve coïncide avec le résultat de l’évaluationdu circuit booléen correspondant.

ThéorèmeTraduction de AC i vers CCP i appartient à AC0.

1 0 x1 x2

∧3 ¬

∨3


Définition (Traduction de AC i vers CCP i)On pose le problème suivant :

Entrée : Une description d’une famille de circuits booléensappartenant à AC i .

Sortie : Une description d’une famille de circuits de preuvesappartenant à CCP i tels que le résultat de l’évalua-tion via élimination des coupures de chaque circuitde preuve coïncide avec le résultat de l’évaluationdu circuit booléen correspondant.


1 0 x1 x2

∧3 ¬

∨3



1 0 x1 x2

∧3 ¬

∨3

→



1 0 x1 x2

∧3 ¬

∨3

→

b1 b0 DUPL2

NEGCONJ3

DISJ3



1 0 x1 x2

∧3 ¬

∨3

→

b1 b0 DUPL2

NEGCONJ3

DISJ3

⊗

Inclusion des classes de complexité

ThéorèmePour i ∈N, AC i

⊆ CCP i .

RemarquePour i ∈N, CCP i

⊆ mBNi .

RemarqueAC0

⊆ CCP0⊆ AC0(UstCONN2).



⊆ CCP i .


⊆ mBNi .

RemarqueAC0




⊆ CCP i .


⊆ mBNi .

RemarqueAC0


Aubert, C. (2010).Réseaux de preuves booléens sous-logarithmiques.Mémoire de M2 L.M.F.I., Paris VII, L.I.P.N.

Mogbil, V. et Rahli, V. (2007).Uniform circuits, & Boolean proof nets.In Proceedings of L.F.C.S., pages 401–421. Springer.

Terui, K. (2004).Proof Nets and Boolean Circuits.In Proceedings of LICS’04, pages 182–191.

Documents

Réseaux de preuves booléens sous-logarithmiques · Réseaux de preuves booléens sous-logarithmiques Mémoire en vue de l’obtention du M2 L.M.F.I. à l’Université Paris VII