Imaginez un échiquier. Placez-y deux reines rivales de manière qu'elles ne puissent pas s'attaquer directement. Facile ? Eh bien, recommencez en ajoutant six reines de plus. Compliqué, mais possible. Pour finir, étendez le problème à des échiquiers de n'importe quelle taille, avec n'importe quel nombre de reines prédéfini. Le fameux «problème des 1000 reines» n'est rien d'autre qu'un exemple isolé pour expliquer un exercice bien plus complexe, P versus NP, à tel point que l'Institut Clay de mathématiques offre un million de dollars pour la première démonstration positive.
Il existe un concours très intéressant appelé «Les Sept Problèmes du millénaire». Lancé en l'an 2000 par l'Institut Clay de mathématiques, son objectif est de trouver des réponses à sept problèmes classiques qui ont «résisté» à une solution au fil des ans. Jusqu'à présent, le seul problème ayant reçu une démonstration appropriée est la «Conjecture de Poincaré», développée par le mathématicien russe Grigori Perelman.
L'institut n'a pas hésité à lui offrir un million de dollars pour son travail, mais Perelman l'a refusé, disant que sa contribution n'était pas supérieure à celle du mathématicien Richard S. Hamilton, qui avait suggéré une solution auparavant. Un autre des grands problèmes que l'institut souhaite voir résolu est le fameux «P versus NP», et pour essayer de le comprendre, le plus courant est de recourir aux échecs :
Ça n'a pas aidé ? Ne vous inquiétez pas, je n'en ai pas tiré grand-chose au début. P versus NP est plus compliqué que de jeter une paire de reines sur un échiquier, et sa réputation d'impossible est bien justifiée. En termes très relâchés (et je dis «relâchés» en toute sincérité) on peut dire que les problèmes dits P sont faciles à résoudre et à vérifier avec des algorithmes, dans un «temps polynomial».
D'autre part, les problèmes NP sont faciles à vérifier pour savoir si leur solution est correcte ou non, tandis que les atteindre demande beaucoup de temps et d'efforts, avec des pertes notables d'efficacité. Des exemples robustes de problèmes NP sont les casse-tête, le Sudoku, et même le Démineur. Maintenant : que se passerait-il si vous trouviez la clé pour résoudre un problème NP en temps polynomial, avec une grande efficacité ?
Si vous y parvenez, vous constaterez qu' il n'y a pas de différence entre N et NP (N = NP), ce qui poussera l'Institut Clay (et non l'Université de St. Andrews comme on l'a répété à satiété) à lancer un million de dollars dans votre direction, suivi probablement d'un prix Nobel, et de la haine des experts en cryptographie du monde entier. La plupart des experts penchent pour N ≠ NP, et pour être honnête, beaucoup de choses en dépendent (le chiffrement mentionné plus haut en est une). Mais si vous voulez quand même essayer... bonne chance. Vous en aurez besoin.
