P=NP : Qu'est-ce que c'est ?

[upium666]

Bonjour à tous et à toutes !

Qui peut vulgariser le problème "P=NP" qui a l'air d'être LE problème du millénaire afin que les amateurs de mathématiques comme moi puissent avoir un semblant d'aperçu, au moins une petite idée de ce que c'est ?

Merci

[Sylviel]

De très loin :

On considère un problème résolvable par un algorithme. La question est : peut-on trouver un algorithme qui le résolve en un nombre d'opérations élémentaires (additions, multiplication, division...) Polynomiale en la taille du problème ? Si c'est le cas le problème est de classe P. Sinon il est de classe NP.

On n'a jamais pu montrer qu'un problème est réellement de classe NP, tout ce qu'on sait faire c'est dire qu'il est "aussi difficile" qu'un problème que tout le monde pense dur donc de classe NP. Et le problème "P=NP" serait de dire si oui ou non il existe des problème que l'on ne peut pas résoudre en temps polynomiale (idéalement en donnant un algo polynomiale pour résoudre un des problèmes dis NP).

Mais ce n'est pas le seul problème phare des mathématiques contemporaines...

[upium666]

De très loin :

On considère un problème résolvable par un algorithme. La question est : peut-on trouver un algorithme qui le résolve en un nombre d'opérations élémentaires (additions, multiplication, division...) Polynomiale en la taille du problème ? Si c'est le cas le problème est de classe P. Sinon il est de classe NP.

On n'a jamais pu montrer qu'un problème est réellement de classe NP, tout ce qu'on sait faire c'est dire qu'il est "aussi difficile" qu'un problème que tout le monde pense dur donc de classe NP. Et le problème "P=NP" serait de dire si oui ou non il existe des problème que l'on ne peut pas résoudre en temps polynomiale (idéalement en donnant un algo polynomiale pour résoudre un des problèmes dis NP).

Mais ce n'est pas le seul problème phare des mathématiques contemporaines...

C'est clair, merci !

Question : qu'est-ce qu'un temps polynomial ? (une question en amène une autre ... :we: )