2.2 Complexité des Problèmes
49
© Dunod – Toute reproduction non autorisée est un délit.
avec une complexité O(1) en effectuant une division de n par 2. Pour le problème du
plus court chemin, nous verrons (dans la partie dédiée aux parcours dans les graphes)
comment un parcours en largeur de G non valué permet de déterminer les plus courts
chemins issus de a. En comparant la valeur trouvée pour le sommet b avec l’entier
B fourni dans la donnée du problème, nous obtenons un algorithme de complexité
O(m 1 n) répondant à la question posée. En revanche, pour ce qui concerne les problèmes du plus long chemin et du cycle hamiltonien, la recherche d’un algorithme
polynomial pouvant les résoudre est restée vaine jusqu’à ce jour. Nous allons voir
dans le paragraphe ci-après qu’un des principaux résultats de la théorie de la complexité permet de conjecturer que de tels algorithmes n’existent pas.
Nous allons maintenant définir NP, la classe des problèmes de décision pouvant
être résolus en temps polynomial par un algorithme non déterministe. Plutôt que de
définir la notion d’algorithme non déterministe, nous allons donner une définition
de la classe NP ne faisant appel qu’aux algorithmes déterministes. Un problème de
décision appartient à NP si et seulement si pour toute instance (jeu de données) du
problème ayant pour réponse « oui », il existe un certificat
1
(ce certificat est donné)
permettant, avec un algorithme en temps polynomial, de vérifier que la réponse au
problème est effectivement « oui ».
Voici quelques exemples. Considérons le problème du plus court chemin (de a
à b dans un graphe non valué) ; il est aisé de concevoir un algorithme polynomial
vérifiant si chemin de a à b (c’est le « certificat » utilisé pour ce problème) a une
longueur inférieure à B. De façon identique, pour le problème du plus long chemin
élémentaire, il est possible de vérifier, par un algorithme polynomial si un chemin
donné est élémentaire, s’il relie effectivement a et b et s’il est de longueur supérieure
à B. Ces deux problèmes appartiennent donc à NP. De même, pour le problème du
cycle hamiltonien, lorsqu’un graphe G admet un cycle hamiltonien, en prenant un
tel cycle pour certificat, il est possible de vérifier en temps polynomial que ce cycle
passe effectivement une et une seule fois par tous les sommets de G.
Considérons le problème de décision de la non primalité défini de la façon suivante. La donnée est n un nombre entier et la question est « n est-il divisible par
un entier autre que 1 et lui-même ? » Montrons que ce problème appartient à NP.
Premièrement nous considérons une instance de ce problème ayant pour réponse
« oui », c’est-à-dire un entier n qui n’est pas premier. Lorsque n n’est pas premier,
il admet pour diviseur un entier a, a 2 1, a 2 n ; en prenant cet entier a comme
certificat, la division de n par a pouvant s’effectuer avec un algorithme polynomial,
nous en concluons que ce problème est dans la classe NP. Considérons maintenant
le problème complémentaire, le problème de la primalité dans lequel la donnée est n
un nombre entier et la question : « n est-il premier ? » Ici la détermination d’un certificat permettant la vérification en temps polynomial de la primalité de n est moins
aisée. Le lecteur intéressé pourra consulter la démonstration de l’appartenance à NP
du problème de la primalité dans des ouvrages spécialisés consacrés à la théorie de
la complexité.
1. Nous verrons dans les exemples suivants le sens que l’on donne ici au terme « certificat ».
49
© Dunod – Toute reproduction non autorisée est un délit.
avec une complexité O(1) en effectuant une division de n par 2. Pour le problème du
plus court chemin, nous verrons (dans la partie dédiée aux parcours dans les graphes)
comment un parcours en largeur de G non valué permet de déterminer les plus courts
chemins issus de a. En comparant la valeur trouvée pour le sommet b avec l’entier
B fourni dans la donnée du problème, nous obtenons un algorithme de complexité
O(m 1 n) répondant à la question posée. En revanche, pour ce qui concerne les problèmes du plus long chemin et du cycle hamiltonien, la recherche d’un algorithme
polynomial pouvant les résoudre est restée vaine jusqu’à ce jour. Nous allons voir
dans le paragraphe ci-après qu’un des principaux résultats de la théorie de la complexité permet de conjecturer que de tels algorithmes n’existent pas.
Nous allons maintenant définir NP, la classe des problèmes de décision pouvant
être résolus en temps polynomial par un algorithme non déterministe. Plutôt que de
définir la notion d’algorithme non déterministe, nous allons donner une définition
de la classe NP ne faisant appel qu’aux algorithmes déterministes. Un problème de
décision appartient à NP si et seulement si pour toute instance (jeu de données) du
problème ayant pour réponse « oui », il existe un certificat
1
(ce certificat est donné)
permettant, avec un algorithme en temps polynomial, de vérifier que la réponse au
problème est effectivement « oui ».
Voici quelques exemples. Considérons le problème du plus court chemin (de a
à b dans un graphe non valué) ; il est aisé de concevoir un algorithme polynomial
vérifiant si chemin de a à b (c’est le « certificat » utilisé pour ce problème) a une
longueur inférieure à B. De façon identique, pour le problème du plus long chemin
élémentaire, il est possible de vérifier, par un algorithme polynomial si un chemin
donné est élémentaire, s’il relie effectivement a et b et s’il est de longueur supérieure
à B. Ces deux problèmes appartiennent donc à NP. De même, pour le problème du
cycle hamiltonien, lorsqu’un graphe G admet un cycle hamiltonien, en prenant un
tel cycle pour certificat, il est possible de vérifier en temps polynomial que ce cycle
passe effectivement une et une seule fois par tous les sommets de G.
Considérons le problème de décision de la non primalité défini de la façon suivante. La donnée est n un nombre entier et la question est « n est-il divisible par
un entier autre que 1 et lui-même ? » Montrons que ce problème appartient à NP.
Premièrement nous considérons une instance de ce problème ayant pour réponse
« oui », c’est-à-dire un entier n qui n’est pas premier. Lorsque n n’est pas premier,
il admet pour diviseur un entier a, a 2 1, a 2 n ; en prenant cet entier a comme
certificat, la division de n par a pouvant s’effectuer avec un algorithme polynomial,
nous en concluons que ce problème est dans la classe NP. Considérons maintenant
le problème complémentaire, le problème de la primalité dans lequel la donnée est n
un nombre entier et la question : « n est-il premier ? » Ici la détermination d’un certificat permettant la vérification en temps polynomial de la primalité de n est moins
aisée. Le lecteur intéressé pourra consulter la démonstration de l’appartenance à NP
du problème de la primalité dans des ouvrages spécialisés consacrés à la théorie de
la complexité.
1. Nous verrons dans les exemples suivants le sens que l’on donne ici au terme « certificat ».