Compte rendu

Une classe de problème NP :

NP-complets problème le  plus dure

trouver la solution exponentiel

verifier la solution linéaire

ex :

décomposition en facteurs premiers

trouver la solution dure(taille du nombre/temps augmente grandement)

verifier la solution simple

base du chiffrement RSA

Classe de complexité du problèmes

Classe P = polynomiale

Compléxité N,N²,……,N

Classe NP=exponentiel :

2exposantN

« Vérification facile »

« dure à résoudre »

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                [pic 1][pic 2][pic 3][pic 4]

évolution de la technologie grossissement de la classe P

le question est est ce qu il y a des algorithme polynomial pour résoudre des algorithme exponentiel ou est ce que il restera toujours des algorithme impossible à faire en polynomial

Et bien si cela est vrais cela voudrais dire que tout problèmes facle à vérifier est d’une façon ou d’un autre facile à résoudre

D’ou le problème p=np pour répondre à cette question

Pour résoudre ce problème on peu résonner par l’absurde

montrer qu’un problème NP est impossible mathématiquement à P personne n’a réussi encore à ce jour, cela voudrait donc dire qu’il faudrait résoudre tout les problé NP avec P

Trop de temps existaence de problèm euniverselle :

Problème SAT si on arrive à résoudre se problème avec P on arriverais a résoudre tout les problèmes NP

Problème SAT problème de satisfaisablité

Si une éxigence 1-SAT

2 exigence 2-SAT

Problème SAT pour liste N d’éxigence et que au moins une soit fait, algorithme trouvant les solutions pas d’algorithme encore trouver avec temps polynomiale

problèmes NP complets kuk len

si on arrive à résoudre un problème NP complet en complexité polynomiale on aura résoud le problème p=np

parmis tout les algorithme à 1million de dollars permettrait de débloqué beaucoup de chose

présentation du problème

1. présenter ses enjeux
2. avec des exemples de problèmes, définir termes
3. temps plynomial
4. P
5. NP

1. JAZ2231Aujourd’hui à 16:22[pic 5][pic 6][pic 7][pic 8][pic 9][pic 10][pic 11][pic 12][pic 13][pic 14][pic 15][pic 16][pic 17][pic 18][pic 19][pic 20]

les classes de complexité

1. P
2. n^xonstante
3. Classe P = Polynomiale
4. N
5. --> problèmes faciles ou rapide à résoudre
6. = temps polynomial
7. classe NP ( attention NP c''est pas Non polynomial , c'est Non déterministe polynomial ) (modifié)
8. problèmes compliqués à résoudre
9. 2^N
10. non déterministe polynomial = facile à vérifier
11. nombreux problèmes résolus par des algorithmes
12. et ces algorithmes ont des complexités différentes
13. rappel complexité
14. présentation classe P avec exemple ( tri) ( temps polynomial ) (modifié)
15. présentation classe NP avec exemple ( sac à dos ) (modifié)
16. problèmes qui ne sont pas NP
17. classification évolutive
18. ex ( test de primalité devenu P )
19. (( N^12 AKS chercheurs indiens ))
20. ((N^6))
21. question P va t'il englober NP ?
22. se confondre dans NP
23. existe-il des problèmes NP non résolvables dans un temps polynomial ? ( mathématiquement , absolu ) (modifié)
24. ou pour chaque NP un algo polynomial qu'il suffirait de trouver ?
25. implication = tout problème vérifiable dans un temps polynomial peut être résolu dans un temps polynomial
26. 7 problèmes du millénaire de l'institut Clay = 1M de dollars
27. ( vous pouvez essayer)
28. P=NP
29. serait-ce une seule classe ?
30. ----------
31. recherche solution
32. -trouver borne inférieure
33. --> montrer pour un problème NP qu'il est impossible de le résoudre en temps polynomial
34. borne inférieure du tri c'est n * log(n)
35. personne n'a réussi car c'est peut être faux ?
36. 1problème : infinité de problèmes , on peut pas tous les démontrer
37. ça semble impossible mais il existe des problèmes NP-complets
38. = problèmes particuliers qui sont en quelque sorte universels
39. ex SAT
40. --> tous les problèmes NP peuvent être ramenés au problème SAT (*)
41. fonctionnement problème SAT
42. algo de décision
43. satisfaisabilité
44. soit conflit soit pas conflit
45. 2-SAT
46. SAT avec listes d'exigences
47. le problème est de savoir si il y a une solution possible
48. aujourd'hui , on résout ce problème en temmps non polynomial ( donc pas dans P ) (modifié)
49. par contre, on peut facilement vérifier si une suggestion est valide ou non
50. non résolvable en temps polynomial vérifiable en temps polynomial = problème NP (modifié)
51. on peut transformer ce problème mathématiquement
52. en satisfactions de formules de logique booléenne
53. Ce qui fait son importance c'est que 2 informaticiens dans les années 70: Cook et Levin ont montré que ce problème est tellement générique que tout les problèmes NP peuvent être ramenés au problème SAT
54. -------------> donc résoudre le problème en temps polynomial , ça permet de résoudre n'importe quel problème NP en temps polynomial
55. cette propriété porte le nom de NP-complet
56. ( existe plusieurs problèmes NP complet )
57. 23:30
58. shéma
59. schéma*
60. si un problème NP est dans P = bingo
61. ça semble simple :
62. -soit on montre qu'un problème NP-complet est dans P, dans ce cas P=NP
63. -ou problème NP dont on démontre qu'il est impossible de le résoudre en temps polynomial
64. (dans ce cas P n'est pas égal à NP )
65. --> ce problème donne le semntiment qu'il est à la portée de tou
66. NB: 3 cas possible ( indécidabilité dans ZFC)
67. Le fait qu'il soit très difficile de trouver une démonstration à P = NP ou P ≠ NP peut amener à envisager que ce problème soit indécidable
68. Un problème indécidable est un problème dont la véracité ou la fausseté n'admet aucune démonstration dans un système formel donné
69. Conséquences qu'auraient sa démonstration :
70. si on prouve que P=NP
71. et que cette démonstration fournisse un algorithme polynomial pour n'importe quel problème NP
72. --->on pourrait factoriser grands nombres en temps polynomial
73. Or
74. NOUVEAU
75. le fait qu'on ne puisse pas factoriser en temps polynomial est la base de la sécurité bancaire ( si le temps polynomial est faible) (modifié)
76. En effet, le chiffrement RSA est basé là dessus
77. pourrait aussi résoudre le problème de repliment des protéines en temps polynomial
78. (épargner maladies)
79. =>prouver que P=NP serait révolutionnaire
80. WARNING : 2trucs qui limitent cet espoir de hacker toutes les banques
81. -algorithmes polynomiaux ne veut toujours pas dire rapide
82. ex n^7999 est polynomial mais pas rapide
83. donc un telle démo ne pourrait avoir que des conséquences théoriques
84. les plupart des chercheurs pensentque P est différent de NP
85. selon sondage 2019 auprès de chercheurs 88% pensaient que c'était faux et pour les experts du domaine, 99% pensaient que c'était faux
86. toutefois une conjecture ne veut rien dire et rien ne dit qu'on n'y arrivera un jour
87. [pic 21][pic 22][pic 23][pic 24][pic 25][pic 26][pic 27][pic 28][pic 29][pic 30][pic 31][pic 32][pic 33][pic 34][pic 35][pic 36][pic 37][pic 38][pic 39][pic 40][pic 41][pic 42][pic 43][pic 44][pic 45][pic 46][pic 47][pic 48][pic 49][pic 50][pic 51][pic 52][pic 53][pic 54][pic 55][pic 56][pic 57][pic 58][pic 59][pic 60][pic 61][pic 62][pic 63][pic 64][pic 65][pic 66][pic 67][pic 68][pic 69][pic 70][pic 71][pic 72][pic 73][pic 74][pic 75][pic 76][pic 77][pic 78][pic 79][pic 80][pic 81][pic 82][pic 83][pic 84][pic 85][pic 86][pic 87][pic 88][pic 89][pic 90][pic 91][pic 92][pic 93][pic 94][pic 95][pic 96][pic 97][pic 98][pic 99][pic 100][pic 101][pic 102][pic 103][pic 104][pic 105][pic 106][pic 107][pic 108][pic 109][pic 110][pic 111][pic 112][pic 113][pic 114][pic 115][pic 116][pic 117][pic 118][pic 119][pic 120][pic 121][pic 122][pic 123][pic 124][pic 125][pic 126][pic 127][pic 128][pic 129][pic 130][pic 131][pic 132][pic 133][pic 134][pic 135][pic 136][pic 137][pic 138][pic 139][pic 140][pic 141][pic 142][pic 143][pic 144][pic 145][pic 146][pic 147][pic 148][pic 149][pic 150][pic 151][pic 152][pic 153][pic 154][pic 155][pic 156][pic 157][pic 158][pic 159][pic 160][pic 161][pic 162][pic 163][pic 164][pic 165][pic 166][pic 167][pic 168][pic 169][pic 170][pic 171][pic 172][pic 173][pic 174][pic 175][pic 176][pic 177][pic 178][pic 179][pic 180][pic 181][pic 182][pic 183][pic 184][pic 185][pic 186][pic 187][pic 188][pic 189][pic 190][pic 191][pic 192][pic 193][pic 194][pic 195][pic 196][pic 197][pic 198][pic 199][pic 200][pic 201][pic 202][pic 203][pic 204][pic 205][pic 206][pic 207][pic 208][pic 209][pic 210][pic 211][pic 212][pic 213][pic 214][pic 215][pic 216][pic 217][pic 218][pic 219][pic 220][pic 221][pic 222][pic 223][pic 224][pic 225][pic 226][pic 227][pic 228][pic 229][pic 230][pic 231][pic 232][pic 233][pic 234][pic 235][pic 236][pic 237][pic 238][pic 239][pic 240][pic 241][pic 242][pic 243][pic 244][pic 245][pic 246][pic 247][pic 248][pic 249][pic 250][pic 251][pic 252][pic 253][pic 254][pic 255][pic 256][pic 257][pic 258][pic 259][pic 260][pic 261][pic 262][pic 263][pic 264][pic 265][pic 266][pic 267][pic 268][pic 269][pic 270][pic 271][pic 272][pic 273][pic 274][pic 275]

...