Résolution de problèmes NP-complet

    Les problèmes NP-complets recouvrent une très grande partie dans le domaine de recherche Informatique : SAT (satisfaction d'expressions booléennes), CSP (problèmes de satisfaction de contraintes), Programmation Linéaire, Programmation par Contraintes, Théorie des Graphes,Combinatoire, etc. Imaginons que l'on ait un ensemble fini d'une part et une propriété logique "facile" à vérifier d'autre part, laNP-complétude serait alors la question de savoir s'il existe ou non un élément de cet ensemble satisfaisant cette propriété. Il s'agitdonc d'un problème décisionnel. Le premier problème NP-complet, la satisfiabilité d'une formule logique binaire, a été établi en 1971par Stephen Cook. Depuis lors, de nombreux autres problèmes NP-complets ont été identifiés ou prouvés mais certains (beaucoup enréalité !) sont considérés comme intraitables par les ordinateurs (voir la satisfaction d'une formule de logique, la coloration d'ungraphe, la couverture des sommets, les cycles hamiltoniens). L'impossibilité de traiter certains problèmes théoriques est liée au fait que P=NP est toujours au stade de conjecture (elle n'a pas encore été démontré). Déterminer si un ordinateur est capable de "trouverune réponse" ou "prouver sa véridicite" indifféremment et avec la même rapidité est généralement considéré comme la question irrésolue la plus importante dans la "theoretical computer science".

    Malheureusement le monde industriel ne peut pas attendre indéfiniment et heureusement l'Informatique n'est pas uniquement de lathéorie ! En pratique des progrès effectifs et constants ont été accomplis pour résoudre ces problèmes fondamentaux et stratégiquespour de nombreuses applications industrielles. La Programmation par Contraintes, avec ses outils et ses heuristiques, en est un exemple.

    Le classement NP-complet contient les problèmes les plus difficiles de NP ("Non-deterministic Polynomial time"~: il s'agit de l'ensemble des problèmes décisionnels pouvant être résolus en temps polynomial avec une machine de Turing non-déterministe, ils peuvent également être validés par un algorithme polynomial). Ces problèmes semblent vraiment ne pas faire partie de P (bien
que à l'heure actuelle on ne possède pas une réponse définitive, voir la question irrésolue P=NP). Si nous sommes capables de trouver un moyen de résoudre efficacement (algorithme polynomial) un problème de NP-complet, nous pouvons alors utiliser cet algorithmepour résoudre tous les problèmes de NP.

    En effet, comme pour P et P-complet, un problème X appartient à NP-complet s'il est dans NP et si tout autre problème dans NP peut s'y réduire. On en déduit que une méthode "assez facile" pour prouver que un nouveau problème appartient à NP-complet est de montrer d'abordqu'il est dans NP, ensuite le réduire en un problème connu dans NP-complet. Par conséquent il est très utile de connaître une variétéde problèmes NP-complets~: la liste qui suit en décrit brièvement certains parmi les plus connus.

• n-Queens~: Trouver toutes les combinaisons de n Dames sur un damier de taille nxn de telle sorte qu'aucune de dames ne puisse être attaquée par les autres.
• Knapsack problem~: problème du sac à dos (combinatoire, théorie de la complexité, cryptographie). Pour un ensemble donné d'objets, chaque objet ayant un coût et une valeur, déterminer le nombre de chaque objet à insérer dans une collection de telle sorte que le coût total soit inférieur à un coût donné et que la valeur totale soit la plus grande possible.
• Traveling Salesman problem (TSP)~: problème du voyageur de commerce (optimisation discrète et combinatoire). Pour un ensemble de villes et un prix de voyage entre toute couple de villes, quelle est la route la plus économique qui permet de visiter une fois chaque ville et puis de se retrouver à celle de départ ? 
• Graph Coloring problem~: problème du coloriage du graphe (théorie des graphes, application dans l'emploi du temps, allocation de registres dans le microprocesseurs, reconnaissance d'un motif, ...). Il regroupe plusieurs types de problèmes de coloriage des éléments du graphe : vertex coloring (coloriage des sommets), edge coloring (coloriage des arêtes), list coloring (caque sommet choisit dans une liste de couleurs), total coloring, complete coloring, ... Si on indique pas la méthodologie de coloriage, on sous-entend généralement le problème de coloriage des sommets dans le graphe : existe-t-il une coloration (des sommets) du graphe qui utilise au plus k couleurs ?

    La programmation par contraintes (PPC ou CSP en anglais : Constraint Satisfaction Problem) fournit des méthodes pour la résolution de problèmes définis sur des domaines finis (intervalles de nombres entiers, intervalles d'ensembles, par exemple). Tout problème comporte uncertain nombre de variables, chacune ayant un domaine fini, et un certain nombre de contraintes. De même qu'une contrainte implique une ouplusieurs variables, en définissant les combinaisons autorisées et celles qui sont interdites. Ainsi trouver une solution à un problème par contraintes consiste à affecter une valeur à chaque variable de telle sorte que la totalité des contraintes soit satisfaite. Laprogrammation par contrainte s'avère très utile dans de nombreux domaines de la science et de l'industrie. De même que la PPC est utilisée pour la résolution de nombreux problèmes académiques :

• Problème du sac à dos
• Problème du voyageur de commerce 
• Problème du coloriage de graphe
• ...