P est-t-il égal à NP ?

Le 6 aout 2010, un chercheur Indien de 39 ans a apporté des éléments (une preuve de plus de 100 pages encore en cours de vérification, avec semble-t-il des doutes à ce stade) d'une démonstration de l'un des problèmes les plus importants des mathématiques algorithmiques : P <>NP - c'est à dire : existe-t-il des problèmes pour lesquels il est facile de vérifier si une solution convient, mais très difficile de trouver une solution.


Pour donner une image plus romantique : faut-il les mêmes capacités, et éventuellement un peu de méthode, pour apprécier une symphonie de Mozard ou "l'Etre et le Néant" et pour les écrire ?


P désigne les problèmes dont les solutions peuvent être systématiquement trouvées dans un temps "court" par rapport à la longueur du problème. Par exemple, trier les éléments d'une liste de taille N peut se faire en un temps inférieur à N^2 (il suffit par exemple de parcourir la liste pour chercher les plus petit, puis de parcours le reste de la liste pour cherche le 2e plus petit, etc...).

NP désigne les problèmes pour lesquels il n'existe pas de méthode systématique permettant de les résoudre en un temps "court" (il leur faut un temps exponentiel avec la taille du problème, c'est à dire qu'il devient très rapidement trop long à résoudre, même pour un ordinateur), alors qu'il est possible de vérifier si une solution est la bonne en un temps court. Par exemple, savoir dans quel ordre mettre des valises de tailles différentes pour remplir le plus possible le coffre d'une voiture est un problème difficile : à part essayer toutes les solutions, il n'existe pas de méthode simple assurant un succès rapide dans tous les cas. C'est compliqué  avec 10 valises, très difficile avec 100.000 valises.

Pour savoir si un problème est dans NP, il ne suffit pas d'avoir du mal à trouver une solution : par exemple, la résolution du Rubiks Cube est difficile pour beaucoup de personnes (alors qu'il est très simple de voir s'il a été résolu ou non), mais il existe pourtant des solutions simples et automatisables pour le résoudre. Les chercheurs qui se sont penché sur ces questions ont ainsi identifié un ensemble de problèmes "NP-complets", à la fois difficiles à résoudre, et tels que, si l'un d'entre eux était résolu (c'est à dire si une méthode simple et systématique de résolution était trouvée), alors une méthode simple pour chacun des problèmes "NP" pourrait en être déduite.

Si P n'est pas égal à NP, celà signifie qu'il existera des problèmes dont la solution est facile à vérifier mais pour lesquels personne ne trouvera jamais une solution simple pour les résoudre. Actuellement, on connait actuellement des tas de problèmes durs à résoudre, mais personne n'est sur - à moins que la démonstration de N = NP soit faite - qu'il existe une méthode simple pour leur trouver une solution. Par exemple : remplir un sac ou un coffre, trouver le parcours le plus court possibles passant par une liste de villes, Tétris, gérer des emplois du temps...

Actuellement, la majorité des scientifiques pense que P <> NP, reste à voir si la démonstration de Vinay Deolalikar tient (celà peut prendre du temps, comme ce fut le cas pour le théorème de Fermat, et nécessiter de compléter la preuve actuellement apportée)... Même dans l'hypothèse inverse il aura confirmé la puissance exceptionnelle de l'Inde dans le domaine informatique, et la force du modèle américain de "chasse aux talents"...