Mes lecteurs réguliers savent mon attachement au problème P vs NP. Précisons au passage que dans ma recherche, je n'essaye nullement de m'attaquer à celui-ci, le laissant à des gens bien plus intelligent et obstinés que moi et dont c'est ma spécialité ; je me contente parfois de prouver que tel ou tel problème a tel ou tel degré de complexité (p.ex. dans la hiérarchie arithmétique). Toujours est-il que j'enseigne un peu de complexité et que je lis un peu sur le sujet.

Je suis assez surpris et heureux d'apprendre que sortira prochainement un film nommé Traveling salesman' (dont je suppose qu'il sortira en France sous le nom de Le voyageur de commerce''), dont le scénario serait le suivant : quatre mathématiciens de haut niveau trouvent un algorithme de complexité polynomiale pour le problème du voyageur de commerce (on pense généralement que c'est impossible, mais on a échoué à le démontré depuis 40 ans que le problème a été posé), ce qui veut dire que P=NP. Le gouvernement américain cherche à acheter cet algorithme et à exiger leur secret. Que feront-ils ?

Précisons qu'un algorithme efficace pour résoudre des problèmes NP comme SAT ou la factorisation d'entiers pourrait servir à casser les principaux systèmes de chiffrement de communications. On mesure l'intérêt pour un gouvernement de posséder un tel secret.

Plus d'information sur ce sujet :