"Il ne suffit pas d'être persécuté pour être Galilée, encore faut-il avoir raison." (Gould)
13/04/2011, 11h59
#3
RoBeRTo-BeNDeR
Date d'inscription
juin 2010
Localisation
Niort
Âge
33
Messages
1 182
Re : Problème P = NP
Bonjour, je comprendrai cela comme s'en suit:
Si on peut vérifier une solution à un problème en un temps polynomial peut on alors résoudre ce problème en un temps polynomial?
RoBeRTo
13/04/2011, 13h53
#4
babaz
Date d'inscription
septembre 2005
Messages
590
Re : Problème P = NP
Envoyé par RoBeRTo-BeNDeR
Bonjour, je comprendrai cela comme s'en suit:
Si on peut vérifier une solution à un problème en un temps polynomial peut on alors résoudre ce problème en un temps polynomial?
RoBeRTo
Mais encore ?
Aujourd'hui
A voir en vidéo sur Futura
13/04/2011, 23h43
#5
RoBeRTo-BeNDeR
Date d'inscription
juin 2010
Localisation
Niort
Âge
33
Messages
1 182
Re : Problème P = NP
Ben ca me parait parfaitement clair non...? (après je ne suis pas un spécialiste j'en ai entendu parler 1 fois ou 2)
14/04/2011, 13h59
#6
invitebe0cd90e
Date d'inscription
janvier 1970
Messages
1 412
Re : Problème P = NP
On peut formuler ca en gros comme ca : On se donne un probleme qu'on veut résoudre grâce à un algorithme. Soit N la taille du probleme (en gros c'est un nombre entier qui correspond au nombre de données du problemes).
- Un probleme est P si il existe un algorithme qui fabrique une solution, et dont la complexité est un polynome en N
- un probleme est NP si il existe un algorithme capable de vérifier si un certain element est une solution du probleme ou non, et qui est de complexité polynomiale en N. Notes bien que cet algorithme n'est pas capable de trouver la solution, mais seulement de verifier si un truc donné marche ou non.
Evidemment, un probleme P est en particulier un probleme NP. Le probleme "P=NP" concerne donc la reciproque de cette affirmation.