Thibaut > http://en.wikipedia.org/wiki/P%3DNP si tu ne sais pas à quoi Pollux fait référence ^^

(en deux mots : P est l'ensemble des problèmes solubles par un algorithme classique Polynomial (cf. ma définition plus haut ^^), tandis que NP est l'ensemble des problèmes solubles en temps Polynomial par un algorithme Non-déterministe. Le problème consiste à savoir si ces deux ensembles sont égaux, à savoir si tout problème soluble en temps polynomial par un algo non-déterministe peut nécessairement aussi l'être par un algo déterministe. On pense que ce n'est pas le cas mais ce n'est pas prouvé.

On définit ensuite les problèmes NP-complets, ce sont des problèmes NP dont il est prouvé que s'ils appartiennent à P, alors tous les autres problèmes NP aussi. La méthode classique pour prouver qu'un problème est NP-complet est de se ramener à un autre problème NP-complet connu : montrer que si on avait un algo déterministe polynomial permettant de le résoudre, il serait possible à partir de cet algo d'en construire un autre, également polynomial, qui résout le problème connu.

Actuellement quand un problème est NP-complet les seuls algorithmes déterministes qu'on arrive à trouver pour le résoudre sont exponentiels, enfin il me semble.)