UNIVERSITE DE DSCHANG

Faculté des Sciences

Département Math-Info

Algorithmes Avancés et Complexités

CHAPITRE 5 : NP-COMPLÉTUDE

Rédigé et présenté par :

YEMELI KEMEKA Steave Russel
TAWAT MOUNTAPMBEME Mouhamed
MOUCHIKPOU Ibrahim Cherif
MBOUANDI NJOUONKOU Faissal

Option : Intelligence Artificielle (Master 1)

Sous l’encadrement de :
Pr. KENGNE Vianney

Année académique 2025–2026

Table des matières

Introduction Générale 3

1 Concepts Fondamentaux 4
1.1 Problèmes et Algorithmes . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.1.1 Définitions de base . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.1.2 Exemples de problèmes classiques . . . . . . . . . . . . . . . . . . . 4
1.2 Classes de complexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2.1 Classe P . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2.2 Classe NP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2.3 Classe NP-Complet . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2.4 Classe NP-Difficile . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.2.5 Relation entre les classes . . . . . . . . . . . . . . . . . . . . . . . . 9

2 Réduction Polynomiale 10
2.1 Définition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.2 Quelques exemples de réduction . . . . . . . . . . . . . . . . . . . . . . . . 10
2.2.1 SAT vers 3-SAT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.2.2 3-SAT vers 3-Coloration . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2.3 3-SAT vers Clique . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

3 NP-Complétude 14
3.1 Définition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3.2 Machine de Turing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3.2.1 Machine de Turing déterministe (DTM) et non déterministe (NTM) 15
3.3 Théorème de Cook (Cook–Levin) . . . . . . . . . . . . . . . . . . . . . . . 16

4 Approches de Résolution 18
4.1 Algorithmes d’Approximation . . . . . . . . . . . . . . . . . . . . . . . . . 18
4.2 Heuristiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
4.3 Méta-heuristiques : ACO . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
4.4 Methodes Exactes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
4.4.1 Backtracking (Retour sur trace) . . . . . . . . . . . . . . . . . . . . 21
4.4.2 Branch and Bound (Séparation et Évaluation) . . . . . . . . . . . . 22

1
5 Limites et Défis 23
5.1 Limites actuelles face aux problèmes NP . . . . . . . . . . . . . . . . . . . 23
5.2 Complexité croissante dans les applications réelles . . . . . . . . . . . . . . 23
5.3 Impacts de l’hypothèse P ̸= N P . . . . . . . . . . . . . . . . . . . . . . . . 24
5.4 Contraintes de calcul et limites technologiques . . . . . . . . . . . . . . . . 24

6 Domaines d’Application 25
6.1 Planification et logistique . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
6.2 Jeux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
6.3 Biologie computationnelle . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

Conclusion 26

Bibliographie 27

Fiche de TD 30

Table des figures

1.1 Relations entre les classes de complexité P, NP, NP-complet et NP-difficile 9

2.1 Problème de 3-SAT vers 3-Coloration . . . . . . . . . . . . . . . . . . . . . 12

2.2 Problème de 3-SAT vers Clique . . . . . . . . . . . . . . . . . . . . . . . . 13

3.1 Machine de Turing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

3.2 Machine de Turing déterministe . . . . . . . . . . . . . . . . . . . . . . . . 16
3.3 Machine de Turing non déterministe . . . . . . . . . . . . . . . . . . . . . 16

2
Introduction Générale

La complexité algorithmique est un domaine fondamental de l’informatique théorique

qui étudie les ressources nécessaires à la résolution des problèmes computationnels, no-
tamment le temps et la mémoire. Elle permet de classifier les problèmes en fonction de
leur difficulté et d’évaluer l’efficacité des algorithmes qui leur sont associés. Parmi les no-
tions les plus importantes de cette discipline figure la NP-complétude, qui occupe une
place centrale dans la compréhension des limites du calcul algorithmique.
Les problèmes dits NP-complets sont des problèmes pour lesquels aucune solution
efficace (en temps polynomial) n’est connue à ce jour. Ils sont considérés comme les plus
difficiles de la classe NP, car tout problème appartenant à NP peut être transformé en
un problème NP-complet par une réduction polynomiale. Ainsi, résoudre efficacement un
seul problème NP-complet impliquerait la résolution efficace de tous les problèmes de
NP, ce qui aurait des conséquences majeures sur l’ensemble de l’informatique théorique
et appliquée.
De nombreux problèmes concrets relèvent de cette catégorie, notamment le problème
du voyageur de commerce, le problème du cycle hamiltonien, le problème de la couver-
ture d’ensembles ou encore la satisfiabilité booléenne. Ces problèmes apparaissent dans
des domaines variés tels que la logistique, la planification, la cryptographie, l’intelligence
artificielle et la biologie computationnelle. Leur étude est donc essentielle aussi bien d’un
point de vue théorique que pratique.
L’objectif de ce chapitre est de présenter de manière structurée et approfondie le
concept de NP-complétude. Nous commencerons par introduire les notions fondamen-
tales liées aux problèmes et aux classes de complexité, avant d’examiner les techniques de
réduction polynomiale permettant d’établir la NP-complétude d’un problème. Nous abor-
derons également le rôle des machines de Turing dans la définition formelle des classes P
et NP. Enfin, nous discuterons des approches pratiques utilisées pour traiter les problèmes
NP-complets, ainsi que des limites et défis qu’ils posent dans le contexte du calcul réel.

3
Chapitre 1

Concepts Fondamentaux

1.1 Problèmes et Algorithmes

1.1.1 Définitions de base
En informatique, un problème est une question bien définie à laquelle on cherche une
réponse, généralement formulée de manière mathématique ou logique. Il est caractérisé
par un ensemble d’instances possibles et une condition permettant de déterminer si une
solution est valide pour une instance donnée.
Un algorithme est une suite finie et ordonnée d’instructions non ambiguës permet-
tant de résoudre un problème donné. Un algorithme doit satisfaire plusieurs propriétés
fondamentales : il doit être correct, fini, et applicable à toutes les instances du problème.
On distingue principalement deux grandes catégories de problèmes :
— Problème de décision : un problème dont la réponse est de type oui ou non. Ce
type de problème est central en théorie de la complexité.
— Problème d’optimisation : un problème dans lequel on cherche à maximiser ou
minimiser une certaine valeur, par exemple la longueur d’un chemin ou le coût
total d’une solution.

1.1.2 Exemples de problèmes classiques

Plusieurs problèmes bien connus illustrent ces notions :
— Problème du tri : organiser une liste d’éléments selon un ordre donné (croissant
ou décroissant).
— Problème du plus court chemin : déterminer le chemin de coût minimal entre
deux sommets dans un graphe pondéré, comme dans l’algorithme de Dijkstra.
— Problème du voyageur de commerce (TSP) : trouver la tournée la plus courte
permettant de visiter un ensemble de villes exactement une fois avant de revenir
au point de départ.

4
Université de Dschang NP-Complétude Année 2025–2026

— Problème de satisfiabilité booléenne (SAT) : déterminer s’il existe une affec-

tation des variables d’une formule logique qui la rend vraie.

1.2 Classes de complexité

La théorie de la complexité classe les problèmes en fonction des ressources nécessaires
à leur résolution, principalement le temps de calcul.

1.2.1 Classe P
La classe P (Polynomial Time) regroupe l’ensemble des problèmes qui peuvent être
résolus par un algorithme déterministe en un temps polynomial par rapport à la taille de
l’entrée. Autrement dit, un problème appartient à la classe P s’il existe un algorithme qui
le résout en un temps de la forme O(nk ), où n représente la taille de l’entrée et k une
constante.
Les problèmes de cette classe sont généralement considérés comme faciles ou tractables.
Parmi les exemples classiques de problèmes appartenant à P, on peut citer :
— le calcul du plus court chemin dans un graphe (algorithme de Dijkstra),
— la construction d’un arbre couvrant de poids minimum (algorithmes de Prim ou
de Kruskal),
— le tri d’une liste d’éléments.

1.2.2 Classe NP
La classe NP (Nondeterministic Polynomial Time) regroupe l’ensemble des problèmes
de décision pour lesquels une solution candidate peut être vérifiée en temps polynomial
par une machine déterministe. Autrement dit, même si trouver une solution peut être
coûteux, il est possible de vérifier efficacement si une solution proposée est correcte.
Une autre manière équivalente de définir NP est la suivante : un problème appar-
tient à NP s’il peut être résolu en temps polynomial par une machine de Turing non
déterministe.
Exemple : le problème SAT (satisfiabilité)
Soit F (x1 , x2 , . . . , xn ) une expression logique de n variables. Le problème SAT consiste
à trouver des valeurs vrai ou faux pour chacune des variables xi de telle manière à rendre
vraie l’expression F (x1 , x2 , . . . , xn ).
Un algorithme non déterministe résolvant SAT est comme suit :

For (k = 1; k <= n; k++) {

x_k = choix(vrai, faux);
}
Université de Dschang NP-Complétude Année 2025–2026

Si F(x1, x2, ..., xn) = vrai

alors F est satisfiable
sinon
F n’est pas satisfiable

Considérons une formule booléenne en forme normale conjonctive (CNF) suivante :

F = (A ∨ ¬B ∨ C) ∧ (¬A ∨ B) ∧ (B ∨ C).

Pour n variables, on a 2n combinaisons possibles. Ici, pour n = 3, on obtient 23 = 8

combinaisons.

A B C A ∨ ¬B ∨ C ¬A ∨ B B∨C F
0 0 0 1 1 0 0
0 0 1 1 1 1 1
0 1 0 0 1 1 0
0 1 1 1 1 1 1
1 0 0 1 0 0 0
1 0 1 1 0 1 0
1 1 0 1 1 1 1
1 1 1 1 1 1 1

À partir de ce tableau de vérité, on remarque qu’au moins une ligne rend la formule
F vraie (encodée par la valeur 1). La formule est donc satisfiable.
Dans le cas général, la résolution du problème SAT nécessite l’exploration de toutes
les affectations possibles, soit 2n combinaisons. La complexité temporelle est donc expo-
nentielle.
Comme autres exemples de problèmes appartenant à la classe NP, on peut citer : le
problème du chemin de longueur inférieure ou égale à k, le problème du cycle Hamiltonien
et le problème de la k-colorabilité.

Autres exemples de problèmes dans NP Parmi les autres problèmes classiques

appartenant à la classe NP, on peut citer :
— le problème du chemin de longueur inférieure ou égale à k dans un graphe ;
— le problème du cycle hamiltonien ;
— le problème de la k-coloration d’un graphe.

1.2.3 Classe NP-Complet

Un problème est dit NP-complet s’il vérifie deux conditions :
Université de Dschang NP-Complétude Année 2025–2026

— il appartient à la classe NP ;
— tout problème de NP peut être réduit à ce problème en temps polynomial.
Les problèmes NP-complets sont donc les plus difficiles de la classe NP. L’existence
d’un algorithme polynomial pour un seul problème NP-complet impliquerait que tous les
problèmes de NP sont résolubles en temps polynomial.

Exemple : le problème Vertex Cover

Le problème de la couverture de sommets (Vertex Cover ) est un exemple classique
de problème NP-complet. Il est défini comme suit.
Instance : Un graphe non orienté G = (V, E) et un entier k ∈ N.
Question : Existe-t-il un ensemble de sommets C ⊆ V tel que |C| ≤ k et que pour
chaque arête (u, v) ∈ E, au moins l’un des sommets u ou v appartienne à C ?
Un tel ensemble C est appelé une couverture de sommets.
Le problème Vertex Cover appartient à la classe NP, car si un ensemble C est fourni
comme certificat, il est possible de vérifier en temps polynomial que |C| ≤ k et que chaque
arête du graphe est incidente à au moins un sommet de C.
Pour montrer que Vertex Cover est NP-complet, on effectue une réduction polynomiale
à partir du problème de la Clique.

Rappel : définition d’une clique

Soit G = (V, E) un graphe non orienté. Une clique est un sous-ensemble de sommets
K ⊆ V tel que tout couple de sommets distincts de K est relié par une arête. Autrement
dit, le sous-graphe induit par K est un graphe complet.
Le problème de la Clique consiste à déterminer s’il existe, dans un graphe donné, une
clique de taille au moins k, où k est un entier fixé.
Soit une instance (G, k) du problème Clique. On construit une instance (G, |V | − k)
de Vertex Cover, où G est le graphe complémentaire de G.
On a alors l’équivalence suivante :

G admet une clique de taille k ⇐⇒ G admet une couverture de sommets de taille |V |−k.

La construction du graphe complémentaire et le calcul de |V | − k se font en temps

polynomial. Ainsi, le problème Clique se réduit polynomialement à Vertex Cover.
Le problème Vertex Cover appartient donc à la classe NP et comme le problème de la
clique peut se réduire polynomialement au problème de Vertex Cover alors cela implique
qu’il est NP-complet.

Parmi les autres exemples classiques de problèmes NP-complets, on peut citer :

— le problème de la satisfiabilité booléenne (SAT) ;
Université de Dschang NP-Complétude Année 2025–2026

— le problème de la clique ;
— le problème de la 3-coloration des graphes ;
— le problème du cycle hamiltonien ;
— le problème du voyageur de commerce dans sa version décisionnelle.

1.2.4 Classe NP-Difficile

Un problème est NP-difficile s’il est au moins aussi difficile que les problèmes NP-
complets, sans nécessairement appartenir à NP. Cela signifie que la vérification d’une
solution n’est pas forcément possible en temps polynomial.
Exemples de problèmes NP-difficiles
— Problème du voyageur de commerce (TSP) dans sa version optimisation
: ce problème consiste à trouver l’itinéraire le plus court possible permettant à un
voyageur de visiter un ensemble de villes exactement une fois, puis de revenir à la
ville de départ.
— Problème du sac à dos : on dispose d’un ensemble d’objets, chacun caractérisé
par un poids et une valeur, ainsi que d’un sac à dos de capacité limitée. L’objectif
est de déterminer la combinaison d’objets maximisant la valeur totale sans dépasser
la capacité du sac.
— Problème d’emballage de bacs : étant donné un ensemble d’articles ayant
des volumes différents et une collection de bacs de capacité donnée, l’objectif est
d’emballer tous les articles en utilisant le nombre minimal de bacs.
— Problème de planification d’atelier : ce problème concerne la planification de
tâches sur des machines dans un environnement industriel, où chaque tâche suit un
ordre précis d’opérations et chaque opération doit être exécutée sur une machine
spécifique.
— Problème de coloration de graphe : il s’agit d’attribuer des couleurs aux som-
mets d’un graphe de sorte que deux sommets adjacents ne portent pas la même
couleur, tout en minimisant le nombre total de couleurs utilisées.
— Problème de routage de véhicules : similaire au problème du voyageur de
commerce, ce problème généralise le cas à plusieurs véhicules partant et revenant
à un dépôt commun, avec pour objectif de minimiser le coût total des trajets.
Ces problèmes illustrent la diversité des domaines d’application des problèmes NP-
difficiles. Malgré leur complexité apparente, ils jouent un rôle fondamental dans l’étude
des techniques de résolution de problèmes et dans la conception d’algorithmes efficaces en
pratique.
Université de Dschang NP-Complétude Année 2025–2026

1.2.5 Relation entre les classes

Les relations fondamentales entre les classes de complexité peuvent être résumées
comme suit :
— P ⊆ N P : tous les problèmes qui peuvent être résolus en temps polynomial (classe
P ) peuvent également être vérifiés en temps polynomial (classe N P ). Autrement
dit, si une solution peut être trouvée efficacement, alors sa vérification l’est égale-
ment.
— N P -complet ⊆ N P : par définition, tout problème NP-complet appartient à la
classe N P .
— N P -complet ⊆ N P -difficile : tout problème NP-complet est NP-difficile, mais l’in-
verse n’est pas nécessairement vrai.
Une question fondamentale de l’informatique théorique est celle de savoir si P = N P .
Si cette égalité était vraie, alors tous les problèmes de la classe N P , et en particulier
les problèmes NP-complets, pourraient être résolus en temps polynomial. Toutefois, la
majorité des chercheurs considère que P ̸= N P . Dans ce cas, il existerait des problèmes,
notamment les problèmes NP-complets, pour lesquels il est très peu probable de disposer
d’algorithmes exacts efficaces, c’est-à-dire s’exécutant en temps polynomial.

Figure 1.1 – Relations entre les classes de complexité P, NP, NP-complet et NP-difficile
Chapitre 2

Réduction Polynomiale

La réduction est un outil fondamental pour établir la NP-complétude d’un problème.

Elle permet de montrer comment un problème peut être transformé en un autre, tout en
préservant la difficulté de résolution, et facilite ainsi l’étude des relations entre les classes
de complexité.

2.1 Définition
Un problème A est dit réductible à un problème B s’il existe un algorithme permet-
tant de résoudre A en utilisant un algorithme résolvant B.
Lorsque l’algorithme de réduction s’exécute en temps polynomial, en considérant les
appels à l’algorithme résolvant B comme de complexité constante, la réduction est dite
polynomiale. On dit alors que A est polynomialement réductible à B, et on note :

A ≤p B.

Théorème : la relation de réduction polynomiale est transitive, c’est-à-dire :

P1 ≤p P2 et P2 ≤p P3 ⇒ P1 ≤p P3 .

2.2 Quelques exemples de réduction

2.2.1 SAT vers 3-SAT

SAT :
— Instance : une formule booléenne en forme normale conjonctive (CNF), pouvant
contenir des clauses de longueur quelconque.
— Question : existe-t-il une affectation des variables rendant la formule vraie ?
3-SAT :

10
Université de Dschang NP-Complétude Année 2025–2026

— Instance : une formule booléenne en CNF où chaque clause contient exactement

trois littéraux.
— Question : existe-t-il une affectation des variables rendant la formule vraie ?
L’idée de la réduction consiste à transformer chaque clause de la formule SAT en une
conjonction de clauses à trois littéraux.
Soit une clause
C = (ℓ1 ∨ ℓ2 ∨ · · · ∨ ℓk ), k ≥ 4.

On introduit k − 3 variables auxiliaires t1 , . . . , tk−3 et on obtient la formule :

φi = (ℓ1 ∨ ℓ2 ∨ t1 ) ∧ (¬t1 ∨ ℓ3 ∨ t2 ) ∧ · · · ∧ (¬tk−3 ∨ ℓk−1 ∨ ℓk ).

La formule obtenue est satisfiable si et seulement si la clause initiale l’est. Ainsi, une
instance SAT est satisfiable si et seulement si l’instance 3-SAT construite l’est également.
La complexité de cette réduction est de O(m × k), où m est le nombre de clauses et k
la taille maximale des clauses.

2.2.2 3-SAT vers 3-Coloration

Soit une formule 3-SAT composée de m clauses sur n variables x1 , x2 , . . . , xn . On
construit un graphe G tel que la formule est satisfiable si et seulement si G est 3-coloriable.
La construction s’effectue comme suit :
— pour chaque variable xi , on crée deux sommets vi et vi′ représentant respectivement
xi et ¬xi ;
— trois sommets supplémentaires sont ajoutés pour représenter les couleurs True,
False et Base ;
— des arêtes sont ajoutées de façon à imposer qu’un littéral et sa négation reçoivent
des couleurs différentes ;
— pour chaque clause, des sommets et des arêtes sont ajoutés afin de garantir qu’au
moins un littéral de la clause soit colorié par la couleur True.
La formule 3-SAT est satisfiable si et seulement si le graphe obtenu est 3-coloriable.
La complexité de cette réduction est de O(n + m).
Exemple : Considérons la formule booléenne suivante :

f = (u′ ∨ v ∨ w′ ) ∧ (u ∨ v ∨ w′ )

Cette formule est une instance du problème 3-SAT, composée de deux clauses et de
trois variables booléennes u, v et w.
La représentation associée à cette formule est donnée comme suit.
Université de Dschang NP-Complétude Année 2025–2026

Figure 2.1 – Problème de 3-SAT vers 3-Coloration

2.2.3 3-SAT vers Clique

Soit une formule 3-CNF contenant k clauses. On construit un graphe comportant 3k
sommets, un sommet par littéral et par clause.
Des arêtes sont ajoutées entre deux sommets si et seulement si :
— les sommets proviennent de clauses différentes ;
— les littéraux correspondants ne sont pas complémentaires.
Il existe alors une clique de taille k dans le graphe si et seulement si la formule 3-SAT
est satisfiable. Inversement, toute clique de taille k permet de construire une affectation
satisfaisante.
La complexité de cette réduction est de O(m2 × k), où m est le nombre de clauses.
Exemple : Considérons l’expression booléenne suivante en forme normale conjonctive
à trois littéraux (3-CNF) :

φ = (x1 ∨ ¬x2 ∨ ¬x3 ) ∧ (¬x1 ∨ x2 ∨ x3 ) ∧ (x1 ∨ x2 ∨ x3 ).

La représentation graphique associée à cette formule est donnée à la figure correspon-

dante.
Université de Dschang NP-Complétude Année 2025–2026

Figure 2.2 – Problème de 3-SAT vers Clique

Comme clique sur ce graphe, nous avons la clique de taille 3 indiquée l’un en rouge,
et l’autre en bleu. La complexité est de : O(m2 x k), où m est le nombre de clauses et k
est le nombre maximum de littéraux par clause. Synthèse
La réduction polynomiale est un outil essentiel pour établir la NP-complétude d’un
problème en comparant sa difficulté à celle de problèmes déjà connus. Les exemples étudiés
montrent que de nombreux problèmes, bien que différents en apparence, partagent une
complexité équivalente.
Chapitre 3

NP-Complétude

3.1 Définition
La NP-complétude est un concept fondamental de la théorie de la complexité algo-
rithmique. Elle permet de classer les problèmes de décision en fonction de leur difficulté
et de mieux comprendre les limites du calcul algorithmique. Bien que les problèmes NP-
complets soient réputés difficiles à résoudre de manière exacte, ils apparaissent dans de
nombreux domaines pratiques et constituent un axe majeur de recherche en informatique
théorique.

3.2 Machine de Turing

La machine de Turing joue un rôle central dans la théorie de la NP-complétude, car elle
fournit un modèle théorique rigoureux pour définir ce que signifie résoudre un problème
de manière algorithmique.
Une machine de Turing est un modèle abstrait de calcul capable de manipuler des
symboles sur une bande infinie selon un ensemble de règles. Elle est utilisée pour formaliser
les notions de calcul et d’algorithme.
Son fonctionnement repose sur une tête de lecture et d’écriture qui se déplace sur la
bande, lit des symboles, en écrit de nouveaux et change d’état en fonction d’une table de
transitions.

14
Université de Dschang NP-Complétude Année 2025–2026

Figure 3.1 – Machine de Turing

Sur le plan théorique, une machine de Turing peut simuler tout algorithme informa-
tique, ce qui correspond au principe de calculabilité universelle. Elle permet également
de définir les classes de complexité, telles que P et N P , en mesurant le nombre d’étapes
nécessaires à la résolution d’un problème.

3.2.1 Machine de Turing déterministe (DTM) et non détermi-

niste (NTM)
On distingue deux types principaux de machines de Turing.
Une machine de Turing déterministe (DTM) possède, pour chaque couple (état,
symbole lu), une unique transition possible. Elle suit donc un chemin de calcul unique
jusqu’à l’acceptation ou le rejet.
Université de Dschang NP-Complétude Année 2025–2026

Figure 3.2 – Machine de Turing déterministe

Une machine de Turing non déterministe (NTM) peut, au contraire, disposer de

plusieurs transitions possibles pour un même état et symbole. Elle explore conceptuelle-
ment plusieurs chemins de calcul en parallèle et accepte si au moins un chemin conduit à
une solution.

Figure 3.3 – Machine de Turing non déterministe

La classe N P peut alors être définie comme l’ensemble des problèmes qui peuvent être
résolus en temps polynomial par une machine de Turing non déterministe.

3.3 Théorème de Cook (Cook–Levin)

Le théorème de Cook, également appelé théorème de Cook–Levin, affirme que le pro-
blème de la satisfiabilité booléenne (SAT) est NP-complet.
Plus précisément, ce théorème établit que :
— le problème SAT appartient à la classe NP, car une affectation des variables peut
être vérifiée en temps polynomial ;
Université de Dschang NP-Complétude Année 2025–2026

— tout problème appartenant à la classe NP peut être réduit au problème SAT en

temps polynomial.
L’idée fondamentale de la preuve consiste à montrer que le calcul d’une machine de
Turing non déterministe s’exécutant en temps polynomial peut être encodé sous la forme
d’une formule booléenne satisfiable si et seulement si la machine accepte l’entrée.
Ainsi, le théorème de Cook démontre que SAT est le premier problème NP-complet et
constitue la base des démonstrations de NP-complétude par réduction polynomiale.
Chapitre 4

Approches de Résolution

Dans cette partie, nous présentons différentes approches utilisées en pratique pour
traiter les problèmes NP-complets. Étant donné que ces problèmes sont vraisemblablement
intraitables en temps polynomial (si P ̸= N P ), il est nécessaire de recourir à des stratégies
spécifiques permettant d’obtenir soit des solutions approchées, soit des solutions exactes
dans des cas de taille limitée.

4.1 Algorithmes d’Approximation

Les algorithmes d’approximation produisent, en temps polynomial, des solutions dont
la qualité est garantie par rapport à la solution optimale. Cette garantie est généralement
exprimée à l’aide d’un ratio d’approximation. Ces algorithmes sont particulièrement utiles
lorsqu’une solution proche de l’optimum est suffisante.
Un exemple classique est le problème du sac à dos. Une approche gloutonne consiste
à trier les objets selon leur rapport valeur/poids, puis à les sélectionner dans cet ordre
tant que la capacité du sac n’est pas dépassée.
Un autre exemple concerne le problème du voyageur de commerce (TSP) lorsque
les distances satisfont l’inégalité triangulaire. Dans ce cas, un algorithme polynomial basé
sur la construction d’un arbre couvrant minimum suivi d’un parcours préfixe garantit une
solution dont le coût est au plus deux fois celui de la tournée optimale.
Il est important de noter que certains problèmes NP-complets, comme le problème 3-
SAT, sont difficiles à approximer. Dans certains cas, il est démontré qu’aucun algorithme
d’approximation efficace n’existe, sauf si P = N P .

4.2 Heuristiques
Les heuristiques visent à fournir rapidement une solution acceptable, sans garantie sur
sa proximité avec l’optimum. Elles reposent généralement sur des règles simples ou des

18
Université de Dschang NP-Complétude Année 2025–2026

choix locaux, ce qui les rend rapides et faciles à implémenter.

Pour le TSP, une heuristique classique est celle du plus proche voisin, qui consiste à
partir d’une ville et à visiter successivement la ville non encore visitée la plus proche.
Cette approche permet d’obtenir rapidement une tournée, mais elle peut être éloignée de
la solution optimale.
Les heuristiques servent souvent de solutions initiales pour des méthodes plus avancées,
notamment les méta-heuristiques.

4.3 Méta-heuristiques : ACO

Les méta-heuristiques sont des méthodes générales d’optimisation destinées à résoudre
des problèmes complexes pour lesquels les méthodes exactes sont trop coûteuses. Elles
sont généralement inspirées de phénomènes naturels ou biologiques, tels que l’évolution
naturelle, le comportement collectif des insectes ou des processus physiques. Leur objectif
est de guider la recherche de solutions dans un grand espace de possibilités en évitant
les optima locaux et en améliorant progressivement la qualité des solutions, sans garantir
nécessairement l’optimalité.
Rappel : le problème du voyageur de commerce (TSP) Le problème du voya-
geur de commerce (Travelling Salesman Problem, TSP) consiste à déterminer une tournée
de coût minimal qui visite chaque ville exactement une fois et revient à la ville de départ.
Pour un TSP à n villes, le nombre de tournées possibles est défini par la formule :

(n − 1)!
2

Nombre de villes (n) Nombre de tournées possibles

10 181 440
15 ≈ 43 milliards
20 60 822 550 204 416 000
50 ≈ 3 × 1062 (incomputable)

Ce problème est NP-difficile dans sa version optimisation et constitue un cas d’étude

classique pour les méta-heuristiques.
Application : algorithme des colonies de fourmis (ACO)
L’algorithme des colonies de fourmis (Ant Colony Optimization, ACO) est une méta-
heuristique inspirée du comportement collectif des fourmis. Il est largement utilisé pour
résoudre le TSP en construisant progressivement de bonnes tournées à l’aide de phéro-
mones artificielles et d’informations heuristiques.
Université de Dschang NP-Complétude Année 2025–2026

Principe général de l’algorithme ACO

L’algorithme des colonies de fourmis repose sur l’observation du comportement collectif

des fourmis réelles, capables de trouver des chemins courts entre leur nid et une source de
nourriture grâce au dépôt de phéromones. Les chemins les plus courts sont progressivement
renforcés, car ils sont empruntés plus fréquemment.
Dans le cadre du TSP, chaque fourmi construit une tournée en visitant toutes les villes
une seule fois. Le choix de la ville suivante dépend de la quantité de phéromone présente
sur les arêtes et d’une information heuristique liée à la distance.

Probabilité de transition

À l’itération t, la probabilité qu’une fourmi k située dans la ville i choisisse la ville j

est donnée par :
[τij (t)]α [ηij ]β
pkij (t) = P α β
,
l∈N k [τil (t)] [ηil ]
i

où :
— τij (t) représente la quantité de phéromone sur l’arête (i, j) ;
— ηij = 1/dij est l’information heuristique liée à la distance ;
— Nik est l’ensemble des villes non encore visitées par la fourmi k ;
— α et β contrôlent respectivement l’influence de la phéromone et de l’heuristique.
Cette règle permet de trouver un compromis entre l’exploitation des bonnes solutions
connues et l’exploration de nouvelles solutions.

Mise à jour des phéromones

Une fois que toutes les fourmis ont construit leur tournée, les phéromones sont mises
à jour selon la règle suivante :
m
X
τij (t + 1) = (1 − ρ)τij (t) + ∆τijk (t),
k=1

où ρ est le taux d’évaporation et ∆τijk (t) correspond à la quantité de phéromone déposée

par la fourmi k. Cette quantité est généralement définie par :

 Q

si la fourmi k a emprunté l’arête (i, j),
∆τij (t) = Lk (t)
k

0

sinon.

Les meilleures tournées déposent ainsi davantage de phéromones, renforçant leur at-
tractivité pour les itérations suivantes.
Université de Dschang NP-Complétude Année 2025–2026

Schéma général de l’algorithme ACO

L’algorithme ACO appliqué au TSP peut être résumé par les étapes suivantes :
— initialiser les phéromones sur toutes les arêtes ;
— pour chaque itération :
— construire une tournée pour chaque fourmi ;
— calculer la longueur de chaque tournée ;
— mettre à jour les phéromones ;
— retourner la meilleure tournée trouvée.

Complexité

À chaque itération, une fourmi construit une tournée en O(n2 ). Pour m fourmis, le
coût est donc O(mn2 ). La mise à jour des phéromones est également en O(n2 ).
Pour T itérations, la complexité totale est :

O(T · m · n2 ).

Dans la pratique, on choisit souvent m = n, ce qui conduit à une complexité approximative

de O(T · n3 ), nettement plus efficace que les méthodes exactes exponentielles pour des
instances de taille moyenne.
Outre l’algorithme des colonies de fourmis (ACO), d’autres métaheuristiques sont
classiquement utilisées pour résoudre le TSP :
— Algorithmes Génétiques (GA) : Basés sur les mécanismes de la sélection na-
turelle et de la génétique.
— Recuit Simulé (SA) : Inspiré du processus thermodynamique de refroidissement
des métaux.
— Recherche Tabou (TS) : Utilise une mémoire à court terme pour éviter les cycles
et sortir des optima locaux.
— Optimisation par Essaim Particulaire (PSO) : Repose sur le déplacement
d’un groupe d’agents (particules) dans l’espace de recherche.

4.4 Methodes Exactes

4.4.1 Backtracking (Retour sur trace)
Le backtracking explore l’espace des solutions via une recherche en profondeur (Depth-
First Search) organisée en arbre de décision. Contrairement à la force brute, il abandonne
une branche dès qu’elle devient invalide.
Université de Dschang NP-Complétude Année 2025–2026

Principe et Déroulement

L’algorithme progresse de manière récursive selon quatre étapes clés :

1. Choix : Sélection d’une option basée sur l’état actuel.
2. Validation : Vérification des contraintes. Si elles sont violées, l’algorithme effectue
un backtrack.
3. Retour en arrière : Remontée dans l’arbre pour explorer d’autres alternatives si
une branche est sans issue.
4. Solution : Atteinte d’un état final satisfaisant tous les objectifs.

Application au TSP

Pour le voyageur de commerce, le processus suit cette logique :

— Fixer une ville de départ et initialiser la meilleure distance Dmax = ∞.
— Construire récursivement une tournée en ajoutant des villes non visitées.
— Élagage : Abandonner la branche si le coût partiel dépasse déjà la meilleure solution
connue.
— Mettre à jour la solution optimale dès qu’une tournée complète plus courte est
trouvée.
Limitation : Sa complexité en O(n!) rend cette approche inutilisable pour des pro-
blèmes de grande taille, nécessitant alors l’usage d’heuristiques.

4.4.2 Branch and Bound (Séparation et Évaluation)

Le Branch and Bound est une optimisation du backtracking. Il repose sur deux prin-
cipes :
— Séparation (Branch) : Division du problème en sous-problèmes plus simples.
— Évaluation (Bound) : Calcul de bornes inférieures sur le coût du sous-problème.
Si la borne d’un sous-problème est supérieure à la meilleure solution actuelle, la branche
est élaguée, réduisant ainsi drastiquement l’espace de recherche sans perdre l’optimalité.
Chapitre 5

Limites et Défis

La classification d’un ensemble aussi vaste de problèmes importants comme étant NP-
complets ne constitue pas une simple curiosité théorique. Elle soulève des défis majeurs
et impose des limites concrètes à ce que l’on peut espérer calculer, aussi bien du point de
vue de la recherche fondamentale que de l’ingénierie logicielle.

5.1 Limites actuelles face aux problèmes NP

Le constat est clair : à ce jour, malgré des décennies de recherche menées par les plus
grands spécialistes de l’informatique théorique, aucun algorithme en temps polynomial
n’a été découvert pour un quelconque problème NP-complet. Cette absence de percée
constitue l’un des arguments les plus forts en faveur de l’hypothèse selon laquelle un tel
algorithme n’existe pas. Elle explique également pourquoi la question « P = N P ? »
demeure l’un des plus grands mystères de la science moderne.

5.2 Complexité croissante dans les applications réelles

Le défi posé par la NP-complétude est encore accentué par la croissance massive de la
taille des données dans les applications modernes. La logistique à grande échelle, l’analyse
de génomes contenant des milliards de paires de bases, ou encore la planification de sys-
tèmes industriels complexes génèrent aujourd’hui des instances d’une taille inconcevable
il y a seulement quelques décennies.
Des études empiriques menées sur des problèmes tels que le VRP (Vehicle Routing
Problem) ou le TSP (Traveling Salesman Problem) montrent que les méthodes exactes
deviennent rapidement inutilisables dès que le nombre de villes dépasse une fourchette
comprise entre 25 et 60. Au-delà de ces limites, l’explosion combinatoire rend le temps de
calcul totalement prohibitif, même pour les superordinateurs modernes.

23
Université de Dschang NP-Complétude Année 2025–2026

5.3 Impacts de l’hypothèse P ̸= N P

Face à l’absence de solutions efficaces, la majorité des chercheurs adopte l’hypothèse de
travail selon laquelle P ̸= N P . Bien que cette hypothèse ne soit pas encore démontrée, elle
a des implications fondamentales : les problèmes NP-complets seraient intrinsèquement
intraitables, c’est-à-dire qu’aucun algorithme rapide ne pourrait les résoudre de manière
optimale dans tous les cas.
Admettre P ̸= N P revient à renoncer à l’idée de concevoir un algorithme à la fois
rapide, toujours correct et toujours optimal pour tous les problèmes NP-complets. Cela
entraîne un changement de paradigme, dans lequel l’objectif n’est plus la perfection, mais
la recherche de solutions suffisamment bonnes, obtenues en un temps raisonnable.

5.4 Contraintes de calcul et limites technologiques

On pourrait penser que l’amélioration continue du matériel informatique, notamment
l’augmentation de la puissance des processeurs, permettrait à terme de résoudre ces pro-
blèmes. Il n’en est rien : l’explosion combinatoire dépasse largement les progrès technolo-
giques.
Une machine mille fois plus rapide n’offre qu’un gain très limité sur la taille des
instances traitables. Si une machine actuelle peut résoudre un problème de taille n en une
heure, une machine mille fois plus rapide ne pourra résoudre, dans le même temps, qu’un
problème de taille approximativement n + 10, et non un problème mille fois plus grand.
Ainsi, les améliorations matérielles ne suffisent pas à compenser la croissance expo-
nentielle de l’espace des solutions. En définitive, la résolution des problèmes NP-complets
illustre le compromis fondamental entre optimalité et faisabilité, en combinant méthodes
exactes, heuristiques et méta-heuristiques afin de répondre aux contraintes du calcul réel.
Chapitre 6

Domaines d’Application

6.1 Planification et logistique

Les problèmes NP-complets, tels que la planification des tâches, le problème de routage
des véhicules ou encore le problème de la couverture d’ensembles, sont omniprésents dans
les systèmes de planification et de gestion des ressources. En pratique, les entreprises ont
recours à des algorithmes heuristiques ou à des algorithmes d’approximation afin d’obte-
nir des solutions proches de l’optimum dans des délais compatibles avec les contraintes
opérationnelles.

6.2 Jeux
De nombreux problèmes rencontrés dans les jeux vidéo, tels que la recherche de che-
mins, la planification stratégique ou la prise de décision dans des environnements com-
plexes, relèvent de problèmes NP-complets. Des heuristiques, comme l’algorithme A* ou
les algorithmes génétiques, sont couramment utilisées afin d’optimiser les performances et
de garantir une réactivité suffisante des systèmes.

6.3 Biologie computationnelle

En biologie computationnelle, des problèmes tels que le repliement des protéines ou
l’alignement des séquences d’ADN sont également NP-complets. Pour traiter ces pro-
blèmes, les chercheurs utilisent des méthodes d’approximation, des algorithmes probabi-
listes et des heuristiques, notamment les algorithmes de Monte-Carlo, afin d’obtenir des
résultats exploitables en un temps raisonnable.

25
Conclusion

La NP-complétude nous a permis de mieux comprendre les défis fondamentaux en

théorie de la complexité computationnelle. Nous avons exploré les classes de problèmes
P et NP, soulignant l’importance de la vérification rapide des solutions dans le cadre de
NP. La notion de NP-complétude, ainsi que la distinction entre problèmes NP-complets
et NP- difficiles, révèle la structure des problèmes les plus complexes en informatique.
Nous avons également discuté des techniques de réduction polynomiale, qui sont essen-
tielles pour établir des liens entre différents problèmes, permettant ainsi de prouver la
NP-complétude de nouvelles instances. Ces concepts sont cruciaux non seulement pour la
recherche théorique, mais aussi pour des applications pratiques dans divers domaines tels
que l’optimisation, la cryptographie et l’intelligence artificielle. La NP-complétude repré-
sente un domaine riche et dynamique, où la compréhension des limites computationnelles
nous pousse à développer des algorithmes plus efficaces et à explorer de nouvelles ap-
proches pour résoudre des problèmes complexes. Ces connaissances sont essentielles pour
les chercheurs et praticiens en informatique, car elles éclairent les décisions sur l’approche
à adopter face à des problèmes difficiles dans des contextes réels.

26
Bibliographie

— Garey, M. R., & Johnson, D. S. (1979). Computers and Intractability : A Guide to

the Theory of NP-Completeness. W. H. Freeman.
— Papadimitriou, C. H. (1994). Computational Complexity. Addison-Wesley.
— Arora, S., & Barak, B. (2009). Computational Complexity : A Modern Approach.
Cambridge University Press.
— Cook, S. (1971). The complexity of theorem proving procedures. In Proceedings of
the Third Annual ACM Symposium on Theory of Computing, pp. 151–158.
— Dorigo, M., & Stützle, T. (2004). Ant Colony Optimization. MIT Press.
— Goldberg, D. E. (1989). Genetic Algorithms in Search, Optimization, and Machine
Learning. Addison-Wesley.
— Turing, A. M. (1936). On computable numbers, with an application to the Entschei-
dungsproblem. Proceedings of the London Mathematical Society, 42(2), 230–265.
— Datascientest. Backtracking : tout savoir. [Link]
— YouTube. Vidéos pédagogiques sur la complexité algorithmique : [Link]
[Link]/watch?v=x1sFJ_HKEaI, [Link]
[Link]

27
Fiche de TD

Exercice 1 : Problèmes dans NP ou dans P

Les problèmes suivants sont-ils dans la classe NP ou dans la classe P ? Justifier votre
réponse.
— Problème P1
Données : un graphe G = (V, E).
Question :existe-t-il un cycle de longueur égale à 4 ?
— Problème P2
Données : un graphe G = (V, E), deux sommets distincts u et v de G et un entier
k.
Question : existe-t-il un chemin simple entre u et v de longueur inférieure ou égale
à k?
— Problème P3
Données : un graphe G = (V, E) et un entier k.
Question : existe-t-il un arbre couvrant tous les sommets de G ayant moins de k
feuilles ?

Exercice 2 : Propriétés sur l’ordre de réduction

Soient A et B deux problèmes de décision. Une réduction de A vers B est une fonction
f : IA → IB calculable en temps polynomial telle que w ∈ Oui(A) si et seulement si
f (w) ∈ Oui(B). On note alors A ≤ B.

1. Montrer que la relation ≤ est réflexive.

2. Montrer que la relation ≤ est transitive.
3. Montrer que P = N P si et seulement si 3-SAT ∈ P .

Exercice 3 : Variante du problème 3-SAT

Donnée : une formule F ′ sous forme conjonctive telle que chaque variable apparaisse
au plus trois fois dans F ′ , sous forme positive ou négative.

28
Université de Dschang NP-Complétude Année 2025–2026

Question : décider si F ′ est satisfiable.

1. Soient x1 , x2 , . . . , xk . Considérons la formule φ composée des clauses (xi ∨ ¬xi+1 )

pour i = 1, . . . , k − 1, et de la clause (xk ∨ ¬x1 ). Montrer que φ est satisfaite si et
seulement si xk = x1 .
2. Montrer que ce problème appartient à NP.
3. Montrer que ce problème est NP-complet par réduction depuis 3-SAT.
4. Montrer que 3-SAT reste NP-complet même si chaque variable apparaît exactement
trois fois.
5. Montrer que 3-SAT reste NP-complet même si chaque variable apparaît deux fois
sous forme positive et une fois sous forme négative.

Exercice 4 : Chevaliers de la table ronde

Étant donnés n chevaliers et l’ensemble des paires de chevaliers qui sont de féroces
ennemis, déterminer s’il est possible de les placer autour d’une table circulaire de telle
sorte qu’aucune paire d’ennemis ne soit assise côte à côte.

Exercice 5 : Le problème CHAINE

Données : un graphe non orienté G à n sommets, deux sommets distincts u et v de
G.
Question : G contient-il une chaîne de longueur n/2 entre u et v ?

1. Montrer que le problème CHAINE appartient à NP.

2. Montrer que le problème CHAINE est NP-complet.

Exercice 6 : Le problème du voyageur de commerce

Données : un graphe complet G muni d’une fonction de coût positif d sur les arêtes,
et un entier k.
Question : existe-t-il un circuit visitant chaque ville au moins une fois et dont le coût
total est inférieur ou égal à k ?

1. Montrer que le problème du voyageur de commerce est NP-complet même si la

fonction de coût respecte l’inégalité triangulaire.
2. Montrer que le TSP métrique est NP-complet.
Université de Dschang NP-Complétude Année 2025–2026

Exercice 7 : Coloration de graphe

Une coloration d’un graphe G est une fonction associant à chaque sommet une couleur
telle que deux sommets adjacents n’aient pas la même couleur.

1. Donner un algorithme polynomial coloriant un arbre avec seulement deux couleurs.

2. Le problème k-Arbre-coloration est-il dans P ou NP-complet ?

À partir de maintenant, on suppose que le problème de la 3-coloration est NP-complet.

1. Montrer que le problème de la 2-coloration est dans P.

2. Montrer que le problème de la 4-coloration est NP-complet.

Exercice 8 : Le problème de la somme de sous-ensembles

Données : un ensemble fini d’entiers A = {a1 , a2 , . . . , ak } et un entier t.
Question : existe-t-il un sous-ensemble A′ ⊆ A tel que a∈A′ a = t ?
P

On supposera que le problème de la couverture de sommets est NP-complet.

Exercice 9 : Le problème SET COVER

Données : un ensemble U de u éléments, une collection de sous-ensembles S1 , . . . , St
de U et un entier k.
Question : existe-t-il au plus k ensembles dont l’union est égale à U ?

1. Montrer que ce problème appartient à NP.

2. Montrer que ce problème est NP-complet.