P et NP

  Dans le coin inférieur gauche de cette image extraite de l'épisode "La tête sur l'épaule", on peut apercevoir les lettres P et NP : ces lettres ont une grande importance en informatique et pourraient, pourquoi pas, vous faire devenir riche.

  En informatique, tout comme en mathématiques, chaque problème se décompose en étapes simples. Il faut donc effectuer une succession d'opérations simples, que l'on appelle un algorithme, pour arriver au résultat. Et selon le type de problème, le nombre d'opérations nécessaires peut varier énormément selon la taille des données de départ.

  P et NP désignent des types de problèmes : P regroupe des problèmes "facilement" solubles (tout dépend de la taille des données), où le nombre d'opérations maximum à réaliser dépend d'un polynôme; c'est pourquoi on parle d'augmentation à temps polynomial. Les problèmes de type NP regroupent des problèmes également à augmentation à temps polynomial, mais sur des machines que l'on dit non-déterministes : au lieu d'effectuer une série de calculs, elle en effectue plusieurs à la fois. Ce type de problème n'est pas soluble par un ordinateur à cause du grand nombre de possibilités possibles.

  Une question se pose : les problèmes de classe NP sont-ils aussi de classe P et réciproquement? Cela entraînerait alors l'égalité P=NP, et aurait de grandes conséquences sur la sécurité sur Internet par exemple : de nombreux systèmes de cryptage de données reposent sur le fait que le décryptage du code est de classe NP, et est donc impossible. Si on a P=NP, le décryptage pourrait alors être réalisé, et la sécurité du cryptage serait alors nulle.

  C'est pourquoi ce problème fait partie des 7 problèmes du prix du millénaire, instaurés par l'institut Clay : la résolution d'un de ces problèmes vaudrait à son auteur un prix d'un millions de dollars et beaucoup considèrent que ce problème est le seul des 7 à pouvoir être résolu par un amateur. Alors à vos méninges!

Pour en savoir plus :

*Articles de Wikipédia sur la théorie de la complexité, étudiant les classes de complexité comme P et NP, et sur les problèmes du prix du millénaire.