Résumons : on a NP, l'ensemble des problèmes dont on peut vérifier qu'une solution est la bonne en un temps polynomial. Par exemple pour le problème de la satisfiabilité des formules booléennes (on me donne une formule de la forme c_1 ET c_2 ET c_3 ET ... où c_i est de la forme x_j OU x_k OU ..., les x_j étant des variables booléennes), si on me donne une distribution des variables (on appelle ça un certificat), je suis capable de vérifier en un temps linéaire (donc polynomial) qu'elle met bien ma formule à Vrai.
On a ensuite une sous classe de NP qui s'appelle P : l'ensemble des problèmes qu'on peut résoudre en temps polynomial (on peut donc à fortiori vérifier une solution en temps polynomial : P est bien inclus dans NP).Exemple : 2-SAT, le problème de la satisfiabilité en se limitant à deux variables par clause, mais aussi la plupart des algorithmes que nous rencontrons dans la vie de tous les jours.
Enfin, une autre sous-classe de NP est l'ensemble des problèmes NP-complets : trouver un algorithme polynômial pour l'un d'entre eux revient à trouver un algorithme polynômial pour tous les problèmes de NP. Pour ça, un monsieur très fort a commencé par montrer de manière fort peu simple que le problème de la satisfiabilité était NP-complet puis on a des procédés qui permettent, étant donné un problème, de se ramener à SAT ou à l'un des autres problèmes NP-complet que l'on connait. On trouve toutes sortes de problèmes comme SAT, le voyageur de commerce, le bin-packing, pas mal de choses sur les graphes.
Comme on n'a encore jamais trouvé d'algorithme polynômial pour un de ces problèmes (ce serait montrer P=NP), ils sont considérés comme difficile : soit on explore l'ensemble des solutions (exponentiel donc long), soit on utilise des algorithmes d'approximation s'il en existe, qui garantissent souvent une certaine borne de la solution optimale.
Tout le défi P!=NP à l'heure actuelle est donc de réussir à montrer qu'il y a un problème de NP qui n'est pas dans P (ce que tout le monde croit). Et il y a effectivement 1000000$ à la clé (mais vu le cours du dollar en ce moment...)
[^] # Re: Algorithme génétique ?
Posté par Zakath . En réponse à la dépêche Améliorer les performances du noyau avec un algorithme génétique. Évalué à 5.
Résumons : on a NP, l'ensemble des problèmes dont on peut vérifier qu'une solution est la bonne en un temps polynomial. Par exemple pour le problème de la satisfiabilité des formules booléennes (on me donne une formule de la forme c_1 ET c_2 ET c_3 ET ... où c_i est de la forme x_j OU x_k OU ..., les x_j étant des variables booléennes), si on me donne une distribution des variables (on appelle ça un certificat), je suis capable de vérifier en un temps linéaire (donc polynomial) qu'elle met bien ma formule à Vrai.
On a ensuite une sous classe de NP qui s'appelle P : l'ensemble des problèmes qu'on peut résoudre en temps polynomial (on peut donc à fortiori vérifier une solution en temps polynomial : P est bien inclus dans NP).Exemple : 2-SAT, le problème de la satisfiabilité en se limitant à deux variables par clause, mais aussi la plupart des algorithmes que nous rencontrons dans la vie de tous les jours.
Enfin, une autre sous-classe de NP est l'ensemble des problèmes NP-complets : trouver un algorithme polynômial pour l'un d'entre eux revient à trouver un algorithme polynômial pour tous les problèmes de NP. Pour ça, un monsieur très fort a commencé par montrer de manière fort peu simple que le problème de la satisfiabilité était NP-complet puis on a des procédés qui permettent, étant donné un problème, de se ramener à SAT ou à l'un des autres problèmes NP-complet que l'on connait. On trouve toutes sortes de problèmes comme SAT, le voyageur de commerce, le bin-packing, pas mal de choses sur les graphes.
Comme on n'a encore jamais trouvé d'algorithme polynômial pour un de ces problèmes (ce serait montrer P=NP), ils sont considérés comme difficile : soit on explore l'ensemble des solutions (exponentiel donc long), soit on utilise des algorithmes d'approximation s'il en existe, qui garantissent souvent une certaine borne de la solution optimale.
Tout le défi P!=NP à l'heure actuelle est donc de réussir à montrer qu'il y a un problème de NP qui n'est pas dans P (ce que tout le monde croit). Et il y a effectivement 1000000$ à la clé (mais vu le cours du dollar en ce moment...)