Eugène Asarin, mail , Professeur à l'UFR d’Informatique de l’Université Paris 7 - Denis Diderot, laboratoire LIAFA
Les mardis 30 septembre,
7, 14, 21 octobre, 4 novembre de 9h à12h, Examen 18 novembre
Les mercredis 1 et 15
octobre et 12 novembre de 15h à18h
·
mardi 30 septembre
2003 : salle 203/205 bat 41
·
mercredi 1er octobre
2003 : salle 103 1er étage tour 46
·
a partir du lundi 06
octobre et jusqu'à la fin des cours de tronc commun, EN SALLE 113 1ER
ETAGE TOUR 25/26
Mardi le 18 novembre 2003, 9h-12h, salle 113 1er étage tour 25/26. Notes manuscrites autorisées. Documents imprimés interdits.
Et si vous avez besoin d’une remise à niveau en calculabilité et éléments de la théorie des langages, lisez
· P.Wolper, Introduction à la calculabilité, InterEditions, 2001.
La page du même cours donné par Anca Muscholl en 2000-2002.
Un zoo de 369 classes de complexité de Scott Aaronson (Berkeley).
Merci de m’envoyer d’autres liens.
-----Cours 1 (30/09/2003)-----
1.1. Notion de complexité de problème et ses deux aspects :
1.1.1. Bornes supérieures : trouver une telle borne = trouver un bon algorithme et estimer son coût (c’est un problème d’algorithmique)
1.1.2. Bornes inférieures : trouver une telle borne = montrer qu’aucun algorithme ne peut faire plus vite que cette borne (c’est un problème de la théorie de complexité).
1.2. Exemple de borne inf : pour reconnaître les Palindromes par une machine de Turing à 1 ruban il faut W(n2) opérations
2.1. Modèles de calcul utiles (avec la définition quand une machine décide un langage)
2.1.1.
Machine
de Turing (1 ruban)
2.1.2. Machine de Turing (plusieurs rubans)
2.1.3. Machine de Turing (plusieurs rubans, dont un read-only, un write-only)
2.1.4. Machine de Turing nondéterministes
2.2. Classes de complexité – définitions
2.2.1. Classes de base TIME(f(n)) ; SPACE(f(n)) ; NTIME(f(n)) ; NSPACE(f(N))
2.2.2. Théorème d’accélération
2.2.3. Les classes célèbres (unions des classes de base) L,NL,P,NP,PSPACE, NPSPACE (provisoire), EXP
2.2.4. Le rôle essentiel de la classe P
2.2.5. Remarque sur la dépendance et indépendance des classes de complexité du choix de modèles de calcul.
-----Cours 2 (01/10/2003)-----
2.3. Relations entre classes de complexité
2.3.1. Fonctions sympa (proper functions). On suppose que f est sympa et f>= log
2.3.2. Monotonie : si f<g, alors Classe(f)<Classe(g)
2.3.3. Relations simples : TIME(f) < NTIME(f) ; SPACE(f)<NSPACE(f)
2.3.4. « Déterminisation »NTIME(f) < TIME(kf) ; NTIME(f) < SPACE(f) . Preuve : essayer tous les calculs possibles de la machine nondéterministe.
2.3.5. « Reachability » SPACE(f)<NSPACE(f)<TIME(kf) . Preuve : construire un graphe de configurations (de taille kf) et décider l’atteignabilité (en temps quadratique par rapport à la taille de graphe).
2.3.6.
Théorème de Savitch : Reachability est dans
SPACE(log2(n)).
Preuve : Soit S(x,y,m)=y est atteignable de x par un chemin de
longueur <2m
On a : S(x,y,0)=Arc(x,y) or (x=y) ; S(x,y,m+1)=Existe z (S(x,z,m) and
S(z,y,m) )
Pour un graphe de taille n on a Reachable(x,y)=S(x,y, log n)
On calcule S(x,y, log n) en utilisant les équations de récurrence ci-dessus.
Cela nécessite une pile de profondeur log n, dont chaque élément a une taille
O(log n). Cqfd
2.3.7. Corollaire NSPACE(f) < SPACE(f2). Preuve : construire un graphe de configurations (de taille kf) et décider l’atteignabilité par algorithme de Savitch. Seule difficulté il n y a pas assez de place pour stocker le graphe, il faut donc appliquer l’algorithme à-la-volée sans générer le graphe tout entier.
2.3.8. Corollaire (de tous les points precedents) : L<NL<P<NP<PSPACE=NPSPACE<EXP<NEXP
2.3.9. Classes duales : L dans coClasse ssi complément de L dans Classe
2.3.10. Propriétés des Classes duales : coClasse=Classe pour toutes les classes déterministes ; coNSPACE(f)=NSPACE(f) (théorème de Immerman-Szelepczenyi –sans preuve). Donc la seule classe duale intéressante est coNP. On a P<coNP<PSPACE
2.3.11. Théorèmes d’hiérarchie - pas de preuve encore
2.3.12. Problèmes ouverts : Dans la chaîne 2.3.8 on sait que L≠P et que P≠EXP. Pour les autres inclusions on ne sait pas si elles sont strictes. Le problème le plus connu (et le plus important) est « P=NP ? »
-----Cours 3 (07/10/2003)-----
2.3.13. Théorème
d’hiérarchie et sa preuve par
diagonalisation. Pour
f(n)>=n sympa on a TIME (f) ≠ TIME(f3)
2.3.13.1. Rappel sur la diagonalisation. Le barbier rase ceux et seulement ceux qui ne se rasent pas. R(b,x) ssi not R(x,x) (pour tout x). En particulier pour x=b (est-ce que le barbier se rase) on a R(b,b) ssi not R(b,b)
2.3.13.2. Codage de machines de Turing. On peut toujours représenter un programme d’une telle machine par un mot en alphabet fixe (comment ?). On dénote souvent ce mot, la machine et la fonction calculée par le même symbole.
2.3.13.3. Construction de langage. On le définit L comme suit : M in L ssi la machine M sur l’entrée M donne la réponse «non » avant f(|M|) pas
2.3.13.4. Borne inf. L ne peut pas être dans TIME(F). Preuve : supposons le contraire : L est décidé en temps f(M) par une machine B. Appliquer l’argument de barbier à B pour obtenir une contradiction.
2.3.13.5. Borne sup. L est dans TIME(f3). Preuve : simuler en temps f3 M sur M pendant f(|M|) pas pour pour décider L. CQFD
2.3.13.6. Remarque (gap theorem). Pour les f calculables mais pas sympa le théorème est faux : existe un f tel que TIME(f)=TIME(2f).
3.1.
Réductions
3.1.1.
Idée intuitive de réduction entre problèmes :
A<B
3.1.2.
Utilisation normale (en algorithmique,
programmation, math) : si A<B, et si on sait résoudre B, alors
on sait résoudre A
3.1.3.
Utilisation inverse (en calculabilité,
complexité) : si A<B, et si A est difficile, alors B est aussi
difficile
3.1.4.
Définitions : réductions polynomiales et log-space entre problèmes de
décision
3.1.5.
Propriétés : réflexivité, transitivité.
Fermeture de P, NP, coNP,
PSPACE, EXP par rapport à la réduction polynomiale. Fermeture de toutes les
classes de 2.3.8 par rapport à la réduction log-space.
3.2.
Notion de complétude.
3.2.1.
Definition : A complet dans une classe C si
A appartient à C et tout B dans C se réduit a A (A est un élément
maximal dans le préordre)
3.2.2.
Propriétés : Deux éléments complets dans C
sont équivalents (se réduisent mutuellement). Si A et complet dans C, B
est dans C, et A<B,
alors B est aussi complet.
3.2.3.
Utilisation idéale. Si on arrive à trouver un algo
polynomial pour un des milliers de problèmes NP-complets connus, alors P=NP et
on en déduira des algorithmes polynomiaux pour tous ces problèmes !
3.2.4.
Utilisation typique. Probablement P≠NP.
On prouve qu’un problème A est NP-complet. Donc probablement A n’admet
pas d’algo polynomial.
3.3.
Quelques problèmes utiles
3.3.1.
Formules booléennes. Formules
satisfaisables/valides/contradictoires. Formes normales.
3.3.2.
Problèmes relatives aux formules booléennes. 3SAT<
SAT< SATFormule
3.3.3.
Circuits booléens. Circuits comme formules avec réutilisation de
sous-formules. Circuits comme programmes simples.
3.3.4.
Problèmes relatives aux circuits. SATCircuit.
EvalCircuit
3.3.5.
Bornes sup. 3SAT , SAT, SATFormule, SATCircuit sont
dans NP. EvalCircuit est dans P
3.3.6.
Encore une réduction : SatCircuit< 3SAT
-----Cours 4 (14/10/2003)-----
3.4.
Premiers problèmes complets dans P et NP
3.4.1.
EvalCircuit est P-complet . Méthode de preuve avec tables de
calcul.
3.4.2.
SatCircuit est NP-complet . Même méthode de preuve.
3.4.3.
Théorème de Cook : 3SAT et SAT sont
NP-complets (corollaire de 3.4.2).
3.5.
Autres problèmes NP-complets (preuve par la réduction)
3.5.1.
Les 6 problèmes célèbres (cf Garey & Johnson) - énoncés : 3-MATCHING,
TRANSVERSAL, CLIQUE, ENSEMBLE STABLE, CHEMIN D’HAMILTON, PARTITION
3.5.2.
3-MATCHING est NP-complet : preuve par réduction de 3 SAT.
3.5.3.
3-couverture exacte est NP-complet : On a
une famille de sous-ensembles Ti de {1,…, 3n} avec 3 élements dans
chaque sous-ensemble. Est-il possible de trouver une sous-famille de Ti disjoints et couvrants tout {1,…, 3n}.
NP-complétude : corollaire de 3.5.2
-----Cours 5 (15/10/2003)-----(TD A corrigé)
3.5.4.
TRANSVERSAL est NP-complet : preuve par
réduction de 3 SAT.
3.5.5. PARTITION est NP-complète : preuve par réduction de 3-couverture exacte
3.5.6. Sac-à-dos exacte : On a un ensemble de n entiers et un but B. Existe-t-il un sous-ensemble avec la somme B ? Ce problème est NP-complet : preuve par réduction de Partition.
3.6. Autour de la classe NP
3.6.1. Un algorithme pseudo-polynomial pour le problème précédent : La programmation dynamique donne la complexité O(nB). La NP-complétude est liée à l’utilisation de grands paramètres entiers (exponentiels).
-----Cours 6 (22/10/2003)
3.6.2. Problèmes fortement NP-complets.
3.6.3. Classe coNP, complétude de VALIDITE
3.6.4. NP=coNP ?
3.6.5. Intersection de NP et coNP. Un peu d’histoire (Programmation linéaire. Primalité)
3.7. Problèmes complets dans des classes ?SPACE
3.7.1. Classe L : tout est complet (notre notion de réduction est trop grossière)
3.7.2. Classe NL : complétude de REACHABILITY
3.7.3. Classe PSPACE : complétude de QSAT (et EVALUER- Qformulebooléenne) . Jeux…
-----Cours 7 (04/11/2003)
Compléments de preuve pour 3.7.3 ; correction de TD B et TD C ; complexité uniforme et non-uniforme.
-----Cours 8 (12/11/2003)
3.8. Algorithmes et classes probabilistes
3.8.1. Exemples d’algorithmes probabilistes : Reachability et AB=C
3.8.2. Classes RP et coRP. Algorithmes Monte-Carlo.
3.8.3. Classe ZPP. (intersection de RP et coRP). Algorithmes Las Vegas.
3.8.4. Classe BPP – la plus large classe connue de problèmes pratiquement tractables.
3.8.5. Amplification de probabilité pour RP, coRP, BPP.
3.8.6. Classe PP. Problème MAJSAT est complet (exo : finir la preuve)
3.8.7. Classes probabilistes vs classes « normales ». P<RP<NP<P et dualement P< coRP<coNP<PP
3.8.8. Problèmes ouverts. BPP vs NP.
4.1. Solutions approchées des problèmes complexes
4.2. Hiérarchie polynomiale : structure fine entre P et PSPACE
4.3. Caractérisation logique des classes de complexité.
4.4. Cryptographie, protocoles, preuves interactives.
4.5. Problèmes de très grande et très petite complexité.
4.6. Complexité algébrique
4.7. Complexité de description (Kolmogorov – Solomonoff – Chaitin).
4.8. …
1. Simuler la machine de Turing à plusieurs rubans par la machine à un seul ruban en temps quadratique. Pourquoi une simulation plus efficace est-elle impossible ?
2. Détailler la preuve de 2.3.8
3. Finir la preuve de 3.5.2. Il manque la preuve que si le 3-matching est possible pour le problème construit, alors la formule 3CNF de départ est satisfaisable.
Sujets importants abordés en TD uniquement : complexité de circuits,
complexité non-uniforme
TDA (pour le 14/10/03)
TDB (pour le 21/10/03)
TDC (pour le 4/11/03)
TDD (exo 1 : pour le 12/11/03)
N'hésitez pas de m’envoyer vos commentaires, solutions des exercices, demandes d'information sur le contenu de cours. On apprécierait beaucoup les notes de cours (en tex, html ou même word)