np-complétude - irisapeople.irisa.fr/francois.schwarzentruber/mit1_algo1_2012/... · 2012. 12....
TRANSCRIPT
![Page 1: NP-complétude - IRISApeople.irisa.fr/Francois.Schwarzentruber/mit1_algo1_2012/... · 2012. 12. 5. · Thèse de Cobham-Edmonds problème polynomial = facilement résoluble n1000000?](https://reader035.vdocumento.com/reader035/viewer/2022070219/6129232d714e8712416499d6/html5/thumbnails/1.jpg)
NP-complétude
François SchwarzentruberENS Cachan – Antenne de Bretagne
![Page 2: NP-complétude - IRISApeople.irisa.fr/Francois.Schwarzentruber/mit1_algo1_2012/... · 2012. 12. 5. · Thèse de Cobham-Edmonds problème polynomial = facilement résoluble n1000000?](https://reader035.vdocumento.com/reader035/viewer/2022070219/6129232d714e8712416499d6/html5/thumbnails/2.jpg)
Thèse de Cobham-Edmonds
problème polynomial= facilement résoluble
n1000000 ?
algorithmedu simplexe ?
![Page 3: NP-complétude - IRISApeople.irisa.fr/Francois.Schwarzentruber/mit1_algo1_2012/... · 2012. 12. 5. · Thèse de Cobham-Edmonds problème polynomial = facilement résoluble n1000000?](https://reader035.vdocumento.com/reader035/viewer/2022070219/6129232d714e8712416499d6/html5/thumbnails/3.jpg)
Le paysage
● Plus court chemin● Couverture de
sommets pour les arbres
● Cycle eulérien● 2-coloriage● 2SAT, Horn-SAT
● Plus long chemin● Couverture de
sommets
● Cycle hamiltonien● 3-coloriage● 3SAT
Problèmes faciles
Problèmes “de recherche”
![Page 4: NP-complétude - IRISApeople.irisa.fr/Francois.Schwarzentruber/mit1_algo1_2012/... · 2012. 12. 5. · Thèse de Cobham-Edmonds problème polynomial = facilement résoluble n1000000?](https://reader035.vdocumento.com/reader035/viewer/2022070219/6129232d714e8712416499d6/html5/thumbnails/4.jpg)
3 coloriage
3-coloriage
![Page 5: NP-complétude - IRISApeople.irisa.fr/Francois.Schwarzentruber/mit1_algo1_2012/... · 2012. 12. 5. · Thèse de Cobham-Edmonds problème polynomial = facilement résoluble n1000000?](https://reader035.vdocumento.com/reader035/viewer/2022070219/6129232d714e8712416499d6/html5/thumbnails/5.jpg)
Problème de décision
3-coloriage OUI
![Page 6: NP-complétude - IRISApeople.irisa.fr/Francois.Schwarzentruber/mit1_algo1_2012/... · 2012. 12. 5. · Thèse de Cobham-Edmonds problème polynomial = facilement résoluble n1000000?](https://reader035.vdocumento.com/reader035/viewer/2022070219/6129232d714e8712416499d6/html5/thumbnails/6.jpg)
But de ce cours
● L'humanité ne sait pas s'il existe des algorithmes polynomiaux pour les problèmes de recherche.
● L'humanité sait qu'en résoudre un c'est les résoudre tous.
![Page 7: NP-complétude - IRISApeople.irisa.fr/Francois.Schwarzentruber/mit1_algo1_2012/... · 2012. 12. 5. · Thèse de Cobham-Edmonds problème polynomial = facilement résoluble n1000000?](https://reader035.vdocumento.com/reader035/viewer/2022070219/6129232d714e8712416499d6/html5/thumbnails/7.jpg)
NP
Problème ouvert
P = NP
P
MillenniumPrize
Problems
indécidable...
![Page 8: NP-complétude - IRISApeople.irisa.fr/Francois.Schwarzentruber/mit1_algo1_2012/... · 2012. 12. 5. · Thèse de Cobham-Edmonds problème polynomial = facilement résoluble n1000000?](https://reader035.vdocumento.com/reader035/viewer/2022070219/6129232d714e8712416499d6/html5/thumbnails/8.jpg)
Plan du cours
● S'abstraire de la recherche : le non-déterminisme (NP)
● Réduction pour définir la difficulté (NP-complet)● Le pouvoir de la logique propositionnelle
● Machine de Turing● SAT est NP-complet
● Réduction pour montrer la difficulté● 3-coloriage est NP-complet
![Page 9: NP-complétude - IRISApeople.irisa.fr/Francois.Schwarzentruber/mit1_algo1_2012/... · 2012. 12. 5. · Thèse de Cobham-Edmonds problème polynomial = facilement résoluble n1000000?](https://reader035.vdocumento.com/reader035/viewer/2022070219/6129232d714e8712416499d6/html5/thumbnails/9.jpg)
S'abstraire de la recherche : le non-déterminisme (NP)
![Page 10: NP-complétude - IRISApeople.irisa.fr/Francois.Schwarzentruber/mit1_algo1_2012/... · 2012. 12. 5. · Thèse de Cobham-Edmonds problème polynomial = facilement résoluble n1000000?](https://reader035.vdocumento.com/reader035/viewer/2022070219/6129232d714e8712416499d6/html5/thumbnails/10.jpg)
Un problème qui semble “difficile”
3-coloriage OUI
Les seuls algorithmes qu'on connaisse...● pire cas en temps exponentiel
2100
![Page 11: NP-complétude - IRISApeople.irisa.fr/Francois.Schwarzentruber/mit1_algo1_2012/... · 2012. 12. 5. · Thèse de Cobham-Edmonds problème polynomial = facilement résoluble n1000000?](https://reader035.vdocumento.com/reader035/viewer/2022070219/6129232d714e8712416499d6/html5/thumbnails/11.jpg)
Deviner et tester
Je devineune solution
Je teste sima solutionest correcte
OUI
non-déterminisme
NPen temps polynomial
![Page 12: NP-complétude - IRISApeople.irisa.fr/Francois.Schwarzentruber/mit1_algo1_2012/... · 2012. 12. 5. · Thèse de Cobham-Edmonds problème polynomial = facilement résoluble n1000000?](https://reader035.vdocumento.com/reader035/viewer/2022070219/6129232d714e8712416499d6/html5/thumbnails/12.jpg)
Réduction pour définir la difficulté (NP-complet)
![Page 13: NP-complétude - IRISApeople.irisa.fr/Francois.Schwarzentruber/mit1_algo1_2012/... · 2012. 12. 5. · Thèse de Cobham-Edmonds problème polynomial = facilement résoluble n1000000?](https://reader035.vdocumento.com/reader035/viewer/2022070219/6129232d714e8712416499d6/html5/thumbnails/13.jpg)
Un problème de décision~ un langage
“(abcd)(ab)(ac)(bc)(bd)(cd)”
3-coloriage OUIb c
a
d
![Page 14: NP-complétude - IRISApeople.irisa.fr/Francois.Schwarzentruber/mit1_algo1_2012/... · 2012. 12. 5. · Thèse de Cobham-Edmonds problème polynomial = facilement résoluble n1000000?](https://reader035.vdocumento.com/reader035/viewer/2022070219/6129232d714e8712416499d6/html5/thumbnails/14.jpg)
Réduction... flashback...
Flot
Programmation linéaireTraduction :
Max f12 + f13f12 < 3f13..
![Page 15: NP-complétude - IRISApeople.irisa.fr/Francois.Schwarzentruber/mit1_algo1_2012/... · 2012. 12. 5. · Thèse de Cobham-Edmonds problème polynomial = facilement résoluble n1000000?](https://reader035.vdocumento.com/reader035/viewer/2022070219/6129232d714e8712416499d6/html5/thumbnails/15.jpg)
Réduction pour définir la difficulté
N'importe quel problème NP
ProblèmeNP-dur
Traduction
OUI/NON
![Page 16: NP-complétude - IRISApeople.irisa.fr/Francois.Schwarzentruber/mit1_algo1_2012/... · 2012. 12. 5. · Thèse de Cobham-Edmonds problème polynomial = facilement résoluble n1000000?](https://reader035.vdocumento.com/reader035/viewer/2022070219/6129232d714e8712416499d6/html5/thumbnails/16.jpg)
Conclusion
P
NP
NP-complet
![Page 17: NP-complétude - IRISApeople.irisa.fr/Francois.Schwarzentruber/mit1_algo1_2012/... · 2012. 12. 5. · Thèse de Cobham-Edmonds problème polynomial = facilement résoluble n1000000?](https://reader035.vdocumento.com/reader035/viewer/2022070219/6129232d714e8712416499d6/html5/thumbnails/17.jpg)
Le pouvoir de la logique propositionnelle
● Machine de Turing● Le problème SAT est NP-complet
![Page 18: NP-complétude - IRISApeople.irisa.fr/Francois.Schwarzentruber/mit1_algo1_2012/... · 2012. 12. 5. · Thèse de Cobham-Edmonds problème polynomial = facilement résoluble n1000000?](https://reader035.vdocumento.com/reader035/viewer/2022070219/6129232d714e8712416499d6/html5/thumbnails/18.jpg)
Besoin : parler d'algo formellement... machine de Turing
Je lis 1J'écris 2Je me déplace vers la droite
Je lis 3J'écris 0Je reste sur place
0 1 2 1 2
pub : cours de logique et calculabilité ALGO2, CVFP
![Page 19: NP-complétude - IRISApeople.irisa.fr/Francois.Schwarzentruber/mit1_algo1_2012/... · 2012. 12. 5. · Thèse de Cobham-Edmonds problème polynomial = facilement résoluble n1000000?](https://reader035.vdocumento.com/reader035/viewer/2022070219/6129232d714e8712416499d6/html5/thumbnails/19.jpg)
Je lis 1J'écris 2Je me déplace vers la droite
Je lis 1J'écris 0Je reste sur place
0 1 2 1 2
pub : cours de logique et calculabilité ALGO2, CVFP
Machine de Turing non déterministe
![Page 20: NP-complétude - IRISApeople.irisa.fr/Francois.Schwarzentruber/mit1_algo1_2012/... · 2012. 12. 5. · Thèse de Cobham-Edmonds problème polynomial = facilement résoluble n1000000?](https://reader035.vdocumento.com/reader035/viewer/2022070219/6129232d714e8712416499d6/html5/thumbnails/20.jpg)
Thèse de Church
machine de Turing= ordinateur (non borné)
#?!#
#?!#
![Page 21: NP-complétude - IRISApeople.irisa.fr/Francois.Schwarzentruber/mit1_algo1_2012/... · 2012. 12. 5. · Thèse de Cobham-Edmonds problème polynomial = facilement résoluble n1000000?](https://reader035.vdocumento.com/reader035/viewer/2022070219/6129232d714e8712416499d6/html5/thumbnails/21.jpg)
Le problème SAT
SAT OUI,la formuleest satisfiable
((p et q) → r) et (non r) et p
![Page 22: NP-complétude - IRISApeople.irisa.fr/Francois.Schwarzentruber/mit1_algo1_2012/... · 2012. 12. 5. · Thèse de Cobham-Edmonds problème polynomial = facilement résoluble n1000000?](https://reader035.vdocumento.com/reader035/viewer/2022070219/6129232d714e8712416499d6/html5/thumbnails/22.jpg)
Pourquoi parler de logique ?
SAT
![Page 23: NP-complétude - IRISApeople.irisa.fr/Francois.Schwarzentruber/mit1_algo1_2012/... · 2012. 12. 5. · Thèse de Cobham-Edmonds problème polynomial = facilement résoluble n1000000?](https://reader035.vdocumento.com/reader035/viewer/2022070219/6129232d714e8712416499d6/html5/thumbnails/23.jpg)
Pourquoi parler de logique ?
SAT
0 1 2 1 2
NP
![Page 24: NP-complétude - IRISApeople.irisa.fr/Francois.Schwarzentruber/mit1_algo1_2012/... · 2012. 12. 5. · Thèse de Cobham-Edmonds problème polynomial = facilement résoluble n1000000?](https://reader035.vdocumento.com/reader035/viewer/2022070219/6129232d714e8712416499d6/html5/thumbnails/24.jpg)
N'importe quel problème NP
Théorème de Cook :SAT est NP-dur
Logiquepropositionnelle
Traduction
OUI/NON
![Page 25: NP-complétude - IRISApeople.irisa.fr/Francois.Schwarzentruber/mit1_algo1_2012/... · 2012. 12. 5. · Thèse de Cobham-Edmonds problème polynomial = facilement résoluble n1000000?](https://reader035.vdocumento.com/reader035/viewer/2022070219/6129232d714e8712416499d6/html5/thumbnails/25.jpg)
SAT encode une machine de Turing non-déterministe
Je lis 1J'écris 2Je me déplacevers la droite
Je lis 1J'écris 0Je vaisà droite
1 1 2 1 2
0 1 2 1 2
4 1 2 1 2
4 1 3 1 2
4 2 3 1 2
![Page 26: NP-complétude - IRISApeople.irisa.fr/Francois.Schwarzentruber/mit1_algo1_2012/... · 2012. 12. 5. · Thèse de Cobham-Edmonds problème polynomial = facilement résoluble n1000000?](https://reader035.vdocumento.com/reader035/viewer/2022070219/6129232d714e8712416499d6/html5/thumbnails/26.jpg)
Réductions pour montrer la difficulté
SAT
...Traduction
OUI/NON
![Page 27: NP-complétude - IRISApeople.irisa.fr/Francois.Schwarzentruber/mit1_algo1_2012/... · 2012. 12. 5. · Thèse de Cobham-Edmonds problème polynomial = facilement résoluble n1000000?](https://reader035.vdocumento.com/reader035/viewer/2022070219/6129232d714e8712416499d6/html5/thumbnails/27.jpg)
Variante plus fine : 3-CNF-SAT
SAT
3-CNF-SATTraduction
OUI/NON
![Page 28: NP-complétude - IRISApeople.irisa.fr/Francois.Schwarzentruber/mit1_algo1_2012/... · 2012. 12. 5. · Thèse de Cobham-Edmonds problème polynomial = facilement résoluble n1000000?](https://reader035.vdocumento.com/reader035/viewer/2022070219/6129232d714e8712416499d6/html5/thumbnails/28.jpg)
3-coloriage
3-coloriage OUI
![Page 29: NP-complétude - IRISApeople.irisa.fr/Francois.Schwarzentruber/mit1_algo1_2012/... · 2012. 12. 5. · Thèse de Cobham-Edmonds problème polynomial = facilement résoluble n1000000?](https://reader035.vdocumento.com/reader035/viewer/2022070219/6129232d714e8712416499d6/html5/thumbnails/29.jpg)
3-CNF-SAT
3-coloriage est NP-dur ?
3-COLtraduction
(p ou q ou r)et(p ou (non q))et ...
OUI
![Page 30: NP-complétude - IRISApeople.irisa.fr/Francois.Schwarzentruber/mit1_algo1_2012/... · 2012. 12. 5. · Thèse de Cobham-Edmonds problème polynomial = facilement résoluble n1000000?](https://reader035.vdocumento.com/reader035/viewer/2022070219/6129232d714e8712416499d6/html5/thumbnails/30.jpg)
Un littéral n'est pas rouge !
![Page 31: NP-complétude - IRISApeople.irisa.fr/Francois.Schwarzentruber/mit1_algo1_2012/... · 2012. 12. 5. · Thèse de Cobham-Edmonds problème polynomial = facilement résoluble n1000000?](https://reader035.vdocumento.com/reader035/viewer/2022070219/6129232d714e8712416499d6/html5/thumbnails/31.jpg)
Pour chaque clause, on ajoute :
![Page 32: NP-complétude - IRISApeople.irisa.fr/Francois.Schwarzentruber/mit1_algo1_2012/... · 2012. 12. 5. · Thèse de Cobham-Edmonds problème polynomial = facilement résoluble n1000000?](https://reader035.vdocumento.com/reader035/viewer/2022070219/6129232d714e8712416499d6/html5/thumbnails/32.jpg)
Accroche pour la saison 2
● ALGO1 : introduction à l'algorithmique
● ALGO2
Réductions(NP-complétude)
Paradigme(glouton, dynamique,
etc.)
Structurede données
PSPACE, etc.
Parallélismes,heuristique, proba...
Analyse amortie