Problèmes NP-complet

Algorithmes de référence : Problèmes NP-complet

Définition et notations :
Un problème est dans la classe NP (resp. P) s'il peut être résolu en temps polynomial sur la taille de sa donnée avec un algorithme^* non-déterministe (resp. déterministe).
P⊆NP. On conjecture que P≠NP.
Un problème possède une certification polynomiale quand on peut vérifier en temps polynomial si un candidat-solution (un élément du domaine des solutions) est une solution valide.
Il existe une classe NPC (NP-complet) de problèmes équivalent entre eux qui sont les problèmes de plus grande complexité de NP.
^* Voir la notion de machine de Turing non-déterministe ou déterministe et les modèles de calcul équivalent.

• SAT : une forme clausale (logique) est-elle satisfiable ?
• 3-SAT : une forme normale conjonctives d'au plus trois littéraux (càd variables) est-elle satisfiable.
• 3DM (mariage tri-dimensionnel) : Peut-on réaliser des mariages à trois personnes pour tout le monde en respectant des contraintes de compatibilité. Plus formellement pour trois ensembles A, B, et C de même taille n et M⊆(X×Y×Z) donnés, existe-t-il N⊆M tel que |N|=n et ∀(a,b,c),(a',b',c')∈N a≠a' et b≠b' et c≠c'. Càd
• Partition : peut-on partitionner un ensemble d'objets valués par des entiers naturels entre deux sous-ensembles de même valeur ?
• Recouvrement par sommets : trouver un recouvrement par sommets de taille ≤k donné dans un graphe non-orienté, càd un ensemble de sommets contenant au moins une extrémité de toutes les arêtes.
• Cycle hamiltonien : existe-t-il un cycle élémentaire qui passent par une et une seule fois tous les sommets d'un graphe.
• Clique maximale : trouver une clique (sous-graphe complet) de taille maximale (càd inclus dans aucune autre clique) dans un graphe.
• VRP (voyageur de commerce) : trouver une tournée de longueur minimale sur un ensemble de villes en fonction de leurs distances (=Chemin hamiltonien pondéré).
• Iso-sousgraphe : un graphe possède-t-il un sous-graphe isomorphe à un autre graphe donné.
• Colorabilité : peut-on colorier les sommets d'un graphe avec au plus k couleurs de manière qu'aucune paire de sommets voisins n'ait la même couleur.
• Sac-à-dos : trouver un remplissage de taille maximal (poids ou volume, etc.) d'un sac-à dos de contenance k avec un ensemble de n objets de tailles diverses.

schéma algorithmique RemplirSacàdos
Donnée : un sac-à-dos acceptant au plus k kilogrammes de charge, un ensemble E de n objets de poids donné (entier naturel non nul).
Résultat : un remplissage maximal X du sac.

P← 0;
S← ∅;
Pourchaque X∈2^E (càd chaque sous-ensemble X de E) faire

calculer la somme Q des poids d'objets correspondant;
Si P>Q alors

P← Q;
S← X;

Complexité : O(2ⁿ) qui correspond à la taille de 2ⁿ, domaine d'exploration des solutions.

Certificats : pour tout sous-ensemble de E, on peut vérifier en O(n) s'il est améliorable en essayant d'ajouter chacun des objets restant. Pour toute paire de sous-ensemble de E correspondant à un remplissage maximal du sac-à-dos, on peut vérifier en O(1) lequel est le meilleur.

N.B. pour le problème du voyageur de commerce (cycle ou chemin hamiltonien pondéré) l'espace de solution est l'ensemble des factoriel(n−1) circuits élémentaires contenant tous les sommets d'un graphe complet valué positivement sur les arêtes.