-
Résoudre P vs NP à partir de considérations de base I. La présupposition d’une similarité entre procédure de solution et de vérification
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…