Voici, traduite en français, la définition de la conjecture « P vs NP » telle qu’on la trouve sur Wikipédia en anglais. Partons de la version en anglais car la définition de l’entrée en français est d’emblée assez alambiquée :

« Le problème P vs NP est un problème majeur non résolu en informatique. Il s’agit de savoir si tout problème dont la solution peut être vérifiée rapidement peut également être résolu rapidement. »

Examinons quelques exemples de problèmes dans cette perspective d’une comparaison entre vitesse de résolution et vitesse de confirmation que le problème a bien été résolu.

Premier cas : ce genre de casse-tête où l’on vous propose deux pièces de métal imbriquées en vous mettant au défi de les séparer.… Lire la suite…