Triz dit:En gros, N=NP, on pourrait le traduire comment.
Nan, paske j'aime bien les maths, mais là, je suis un peu largué... 
P=NP
http://fr.wikipedia.org/wiki/Th%C3%A9or ... s#Classe_P (la classe NP est juste derrière)
JE PREVIENS : Y'a sûrement un bon nombre de conneries dans mon gloubiboulga vulgariste qui suit cet avertissement. C'est un mix entre mes souvenirs de cours et mes rafraîchissement via wikipedia. A corriger très certainement, donc.
En gros, tu as plusieurs "classes de complexité" des problèmes mathématiques pour définir le temps que ça va prendre à un ordinateur de le résoudre.
Tu es dans un problème "P" quand c'est compliqué mais que tu peux le résoudre pas l'application de force brute, c'est à dire en essayant toutes les combinaisons. En gros, ton problème se présente sous la forme d'un arbre raisonné dont tu vas parcourir toutes les branches (tu as un point de départ et tu te balades dans ton espace de solutions selon des règles. Prends les échecs : tu as une position de départ et tes possibilités sont limitées).
En gros, la complexité de ces problèmes est dite "polynomiale" parce que leur nombre de solutions est un chiffre porté à une puissance constante (très grande), voire un assemblage de ce type de trucs, à savoir, donc, un polynôme. (r.x^a+s.x^b+...)
Quand tu as un problème de classe "NP", c'est qu'il n'est pas déterministe même s'il est polynomial. Les problèmes P sont un sous-ensemble des problèmes NP, vachement plus durs à résoudre parce qu'il est pas possible de créer un bête arbre à parcourir, ou alors il y a une explosion numérique, je sais plus. De mémoire, le jeu de go est un problème NP. Tu peux pas faire comme aux dames ou aux morpions, tester toutes les solutions, pour le résoudre.
Bref, tu peux pas te fabriquer un big blue qui va tester toutes les combos pour gagner, parce que t'as pas la puissance nécessaire (et de loin) pour ce faire.
Bien sûr, c'est tant que tu restes dans le déterminisme. C'est-à-dire avec des algorithmes.
Les heuristiques sont là pour t'aider. En gros, tu cherche pas vraiment LA solution ultime, mais une solution utile, suffisante (en tout cas dans les problèmes d'optimisation complexes que j'ai eus à résoudre en cours).
Au lieu de tout essayer, tu te balades dans l'espace des solutions plus ou moins aléatoirement en espérant trouver une solution qui te va bien. Bien sûr, tu établis tout un tas de règles pour décider si la solution va bien, et quel chemin tu vas parcourir pour essayer de tomber dessus

Si P=NP, alors en gros on peut tout résoudre sans trop de mal (i.e. dans un temps raisonnable). C'est juste qu'on sait pas forcément comment.
greuh