Cours sur la complexité

Informations

• Publié par: Endrui
• Nombre de lectures: 38
• Langue: Français

Extrait

Emmanuel Jeandel
´COMPLEXITE2`TABLE DES MATIERES
1 Machines de Turing 1
1.1 Machine de Turing classique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Variantes du modele` . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.3 Representation´ des donnees´ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2 Complexite´ en temps et en espace 9
2.1 Definitions´ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2 Theor´ emes` de hierarchie´ - Premieres` relations . . . . . . . . . . . . . . . . . . . . . 11
2.3 Theor´ emes` de hi´ - Diagonalisation . . . . . . . . . . . . . . . . . . . . . . . 12
2.3.1 Espace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.3.2 Temps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
3 Non determinisme´ 19
3.1 Definitions´ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.2 Premieres` propriet´ es´ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3.3 Liens avec les classes deterministes´ . . . . . . . . . . . . . . . . . . . . . . . . . . 21
4 Classes de complexite´ 23
´5 Quelques consequences deP =NP 25
5.1 Factorisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
5.2 Certificats polynomiaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
5.3 Cryptographie - Fonction One-Way . . . . . . . . . . . . . . . . . . . . . . . . . . 28
5.4 Padding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
6 Completude´ 31
6.1 Reductions´ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
6.2 Completude´ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
7 Quelques problemes` NP-complets 39
7.1 Methode´ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
7.2 Variantes de SAT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
7.3 CLIQUE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
7.4 Couplages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
8 Problemes` NP-complets sur les nombres 45
8.1 Une autre variante de SAT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
8.2 SUBSET-SUM et les variantes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
3`4 TABLE DES MATIERES
8.2.1 NP-completude´ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
8.2.2 Un algorithme pour SUBSETSUM . . . . . . . . . . . . . . . . . . . . . . 47
8.3 Problemes` NP-complets au sens fort . . . . . . . . . . . . . . . . . . . . . . . . . 48
9 Algorithmes d’approximation 51
9.1 BINPACKING . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
9.2 PARTITION . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
9.3 KNAPSACK . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
A Index 53
B Liste des definitions´ 55INTRODUCTION
Voici une liste de livres dont je m’inspire pour le cours
– Carton, Langages formels, calculabilite´ et complexite´
– Garey, Johnson, Computers and Intractability, A guide to the Theory of NP-Completeness
– Balcazar, Diaz, Gabarro, Structural Complexity I & II
– Hopcroft, Ullman, Introduction to Automata Theory, Languages and Computation
– Wegener, Complexity Theory
– Kozen, Theory of Computation
– Wagner, Wechsung, Computational Complexity
i`ii TABLE DES MATIERESChapitre 1
MACHINES DE TURING
Le formalisme des machines de Turing permet de definir´ un modele` de calcul precis,´ pour lequel
la notion de complexite,´ et la notion de pas de calcul sera clairement definie.´ Par exemple, il est
difficile d’ev´ aluer exactement combien de temps et de memoire´ un programme C va utiliser sur une
entree´ donnee,´ et il est encore plus difficile de definir´ ce qu’est exactement la notion de temps ou de
memoire.´
Le fonctionnement d’une machine de Turing est tres` proche de ce qui se passe a` bas niveau dans
un ordinateur ordinaire, mais il est enorm´ ement´ simplifie.´
1.1 Machine de Turing classique
Informellement, une machine de Turing consiste en la donnee´ d’un ruban muni d’une teteˆ de
lecture, et d’un etat.´ La de Turing agira en fonction de cet etat´ et de ce qui se trouve sur la
teteˆ de lecture.
Donnons un exemple concret : On considere` la table suivante
a b B
0 (1;b; ) (0;b;!) (1;B;!)
1 (2;b; ) (0;b;!) (3;B; )
2 (1;a; ) (3;a;!) (1;B;!)
3 (1;a; ) (3;a;!) (1;B;!)
` ´Sa signification est la suivante : Si on regarde a la ligne 2,colonneb, on voit marque (3;a;!) ce qui
signifie : si je suis dans l’etat´ 2 et que je lis unb sur ma teteˆ de lecture, alors :
Je passe dans l’etat´ 3
Je mets una a` la place dub
Je deplace´ ma teteˆ a` droite
Un premier exemple d’utilisation est decrit´ dans la figure 1.1. L’etat´ est indique´ a` l’interieur´ de la
teteˆ de lecture. La machine s’arreteˆ lorsqu’elle atteint l’etat´ 3, puisqu’aucune regle` ne specifie´ ce qui
se passe dans ce cas.
12 CHAPITRE 1. MACHINES DE TURING
0 0
::: :::t = 0 B a b a a a a B B B t = 10 B b b b b a a B B B
1 0
::: :::t = 1 B a b a a a a B B B t = 11 B b b b b a a B B B
2 1
::: :::t = 2 B b b a a a a B B B t = 12 B b b b b b a B B B
1 0
::: :::t = 3 B b b a a a a B B B t = 13 B b b b b b a B B B
0 0
::: :::t = 4 B b b a a a a B B B t = 14 B b b b b b a B B B
0 1
::: :::t = 5 B b b a a a a B B B t = 15 B b b b b b b B B B
1 0
::: :::t = 6 B b b b a a a B B B t = 16 B b b b b b b B B B
0 0
::: :::t = 7 B b b b a a a B B B t = 17 B b b b b b b B B B
0 1
::: :::t = 8 B b b b a a a B B B t = 18 B b b b b b b B B B
1 3
::: :::t = 9 B b b b b a a B B B t = 19 B b b b b b b B B B
FIGURE 1.1 – Execution´ d’une machine de Turing1.1. MACHINE DE TURING CLASSIQUE 3
Plus formellement, on definit´ une machine de Turing ainsi :
Definition´ 1.1 (Machine de Turing)
Une machine de Turing a` un ruban est la donnee´ :
D’un ensemble finiQ, appele´ ensemble des etats´ de la machine.Q contient deux etats´
particulier, un etat´ initial note´q et un etat´ final note´q .0 f
D’un alphabet , qui est l’ensemble des symboles qui peuvent apparaˆıtre sur le ruban.
contient un symbole particulier, note´B, correspondant au blanc, c’est a` dire a` une case
vide.
D’un alphabet appele´ alphabet d’entree´
D’une fonction :Q 7!Q f ;!g appele´ fonction de transition.
Exemple
Formellement, l’exemple prec´ edent´ s’ecrit´ ainsi :
Q =f0; 1; 2; 3g.q = 0;q = 30 f
= fa;b;Bg
=fa;bg
est donnee´ par le tableau ci-dessus
Definition´ 1.2
Une configuration d’une machine de Turing est la donnee´ d’un couple constitue´ d’un etat´ et
d’un mot sur contenant exactement une lettre soulignee.´
Au vu de la definition,´ on ne reconnaˆıt pas forcement´ l’objet qu’on a etudi´ e´ sur la figure. L’endroit
souligne´ correspond a` l’endroit ou` se trouve la teteˆ de lecture. Sur la figure, le ruban est infini : il
contient a` la premiere` etape´ BabaaaaBBBB . Dans tous les raisonnements, le ruban sera toujours
constitue´ d’un mot (qui peut contenir des blancs) suivi par une infinite´ de symboles blancs. De sorte
que la configuration (3;BaaB) et la configuration (3;BaaBBBBB) representent´ en fait la memeˆ
configuration,c’est a` dire un ruban ou` se trouveBaaBBB , ou` la teteˆ de lecture est en deuxieme`
position, et ou` l’etat´ de la machine de Turing est l’etat´ 3.
Exemple
La premiere` configuration de l’exemple 1.1 est donnee´ par (0;BabaaaaB) et la derniere` par
(3;BbbbbbbBB).6
4 CHAPITRE 1. MACHINES DE TURING
Definition´ 1.3
0 0SoitM = (Q;q ;q ; ;B; ;) une machine de Turing. Si (q;w) et (q;w ) sont des configu-0 f
0 0 0 0rations, on dit que la machine de Turing passe de (q;w) a` (q;w ), ce qu’on note (q;w)‘ (q;w )
si :
La lettre soulignee´ dansw est la lettre numero´ k.
0 0 (q;w ) = (q;w ;D)k k
08i =k;w =w (Autrement dit, la seule lettre qui change est lakeme)`i i
0 SiD = alors la lettre soulignee´ dansw est la lettre de numero´ k 1. Si au contraire
D =!, c’est la lettre de numero´ k + 1.
On appelle pas de calcul le passage d’une configuration a` la configuration suivante.
Exemple
(0;BbbbaaaBB)‘ (1;BbbbbaaBB). C’est a` dire :
0
:::t = 0 B b b b a a a B B B
1
:::t = 1 B b b b b a a B B B
Definition´ 1.4
0 0 ? 0 0Si (q;w) et (q;w sont deux configurations, on dit que (q;w)‘ (q;w ) s’il existe des confi-
0 0gurations (q ;w )::: (q ;w ) telles que (q ;w ) = (q;w), (q ;w ) = (q;w ) et pour tout1 1 k k 1 1 k k
0 0i, (q;w )‘ (q ;w ). Autrement dit, la machine de Turing passe de (q;w) a` (q;w ) eni i i+1 i+1
plusieurs etapes.´
Exemple
?(0;BabaaaaBB)‘ (3;BbbbbbbBB). C’est a` dire :
0
:::t = 0 B a b a a a a B B B
...
...<