Problème P = NP

[invite4f80dcbf]

Bonsoir,

Vous serait-il possible d'expliquer simplement le problème en question ?

Merci
-----

[Deedee81]

Salut,

Vous serait-il possible d'expliquer simplement le problème en question ?

http://fr.wikipedia.org/wiki/Probl%C3%A8me_P_%3D_NP

[invite332de63a]

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

[invite4f80dcbf]

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 ?

[A voir en vidéo sur Futura]

[invite332de63a]

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)

[invitebe0cd90e]

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.