|  |
 Fanfan - 1806855  Publié le 01/09/2008 à 22:35 
Alors à vos calculettes !!!!
P=NP
Article
 | Fanfan - 1806855 Publié le 01/09/2008 à 22:37
un indice :
les classes de complexité
1)
Un problème de décision est dans P s'il peut être décidé sur une machine déterministe en temps polynomial par rapport à la taille de la donnée. On qualifie alors le problème de polynomial, c'est un problème de complexité O(nk) pour un certain k.
2)
La classe NP des problèmes Non-déterministes Polynomiaux réunit les problèmes de décision qui peuvent être décidés sur une machine non déterministe en temps polynomial. De façon équivalente, c'est la classe des problèmes qui admettent un algorithme polynomial capable de tester la validité d'une solution du problème, on dit aussi capable de construire un certificat. Intuitivement, les problèmes dans NP sont les problèmes qui peuvent être résolus en énumérant l'ensemble des solutions possibles et en les testant à l'aide d'un algorithme polynomial.
On a clairement P = NP car un algorithme déterministe est un algorithme non déterministe particulier, ce qui, dit en mots plus simples, signifie que si une solution peut être calculée en temps polynomial, alors elle peut être vérifiée en temps polynomial. En revanche, la réciproque : NP = P, qui est la véritable difficulté de l'égalité P = NP est l'un des problèmes ouverts les plus fondamentaux et intéressants en informatique théorique. Il a été posé en 1970 indépendamment par Stephen Cook et Leonid Levin[6]. La plupart des spécialistes conjecturent que les problèmes NP-complets ne sont pas solubles en un temps polynomial. À partir de là plusieurs approches ont été tentées.
|
Page 1 
Accueil | Conditions générales | Publicité | FAQ | Contact
| | |
