La NP-complétude en quelques mots
Claude Tadonki,
Chercheur, Mines Paris - PSL (Centre de Recherche en Informatique)
La NP-Completude est probablement le sujet le plus
délicat de l'informatique théorique. En résumé, la question est
de savoir, étant
donné d'une part une propriété logique facile à vérifier,
et d'autre part un sous-ensemble fini ,
s'il existe ou non un élément de cet ensemble qui
satisfait la
propriété. En amont, il s'agit en fait d'un probleme de décision portant sur une instance
donnée pour laquelle on doit se prononcer sur le fait qu'elle satisfait ou non une propriété,
et en fournir une preuve (certificat) facile à vérifier. En pratique, la preuve en elle-meme est ce
qu'on recherche.
Les
ensembles concernés ici sont ceux dont le "noyaux" est
de tres petite
taille et permet de generer tous les elements de
l'ensemble au travers
d'un mecanisme
naturel. C'est le cas par exemple des jeux de
lotterie. Le joueur est
invité
à choisir quelque numéros (rarement plus de dix!)
parmi un ensemble
raisonnable
de valeurs (rarement plus de cinquante!). Le nombre de
combinaisons
possible est
astronimique (meme si on n'en est pas trop conscient
lorsqu'on joue!)
pourtant le
noyau de cet ensemble est visiblement insignifiant (il
tient sur un
bout
de papier!).
Le cas de la lotterie est particulier, car le bon
numéro ne vérifie
aucune propriété
prédéfinie (du moins c'est ce que je pense!). On peut
tout de meme
mettre une logique dans ce
jeu en demandant par exemple de trouver une
combinaison dont la juxtaposition forme un
nombre
premier dont la some des chiffres est paire (toute
lotterie qui s'y essayerait à partir de maintenant
devra me payer mes droits!). Vérifier qu'un
nombre donné est premier est une tache facile (c'est
vrai!), encore
moins que la somme de ses chiffres
est paire. On a donc un jeu qui consiste à
fournir un nombre premier avec une somme de chiffres
qui est paire (facile à vérifier!) dans un espace
dont le noyau tient sur un bout de papier (donc
visiblement abordable!). Je parie que si un tel jeu est lancé,
vous allez tous vous
jeter sur
votre ordinateur et lui demander de traquer la clef du
Pérou.
Rassurez-vous, il y a de forte
chance que la réponse vous vienne toujours de la télé
lors du tirage (comme d'habitude n'est ce
pas ?).
Beaucoup de problemes ont
cette charactéristique, à savoir qu'ils sont d'un réel
intérêt, faciles
à formuler et à "contenir", mais en realite difficiles
à résoudre de maniere déterministe. De
tels
problèmes sont dits NP(-P?) (dans le jargon
de la complexité).
Techniquement, les problèmes NP
peuvent etre
résolus
efficacement si on admet
la possibilité d'explorer simultanement plusieurs
directions. En fait, le chemin qui mène a la solution est "court", mais le problème est de trouver
ce chemin sans se laisser innonder de tentatives infructeuses. C'est comme
dans un labyrinthe, la distance entre le point de depart et la sortie est courte, a condition
de prendre le bon chemin, autrement on risque de parcourir une distance beaucoup plus importante, vraiment beaucoup plus. Parmi les problèmes NP,
il y en a qui ont une proprété toute particulière, ce
sont les problèmes dits NP-complets.
Le sort de tous les problèmes NP est lié à celui des
problèmes NP-complets (les VIP, Very Important Problems). En effet,
si on arrive à prouver (ou à infirmer) la difficulté
intrinsèque d'un probleme NP-complet, il en
sera de même pour tous les problèmes NP (-P).
Le premier
problème NP-complet, la satisfaisabilité
d'une formule logique binaire, a été établi en 1971
par Stephen Cook.
Depuis lors, de nombreux autres problèmes NP-complets
ont été identifiés ou prouvés (liste), par un
mécanisme (transitif) de réduction (lire l'ouvrage de référence Computers and Intractability: A Guide to the Theory of NP-Completeness
(lien)
de Michael R. Garey et David S. Johnson) . Ces problèmes sont
de plus en plus nombreux, beaucoup
plus nombreux que ceux dont les tentatives de résolution attireraient des foules. Prenons un exemple: parmi les
valeurs 4, 5, 12, 17, 6, 11, 7, 9, 15, 18, 8, 11, 3,
19, 1, sauriez-vous me dire s'il existe un
sous-ensemble dont la somme est égale à 37. Je suis sûr que vous avez essayé de trouver ce
sous-ensemble. C'est ainsi, les problèmes NP-complets incitent
toujours à les résoudre. Dans mon exemple
précédent, vous n'allez pas passer le même temps selon
qu'il y a une solution ou non. Ceci est
un autre aspect de la danse. Il est intuitivement
plus aisé de s'en sortir lorsqu'il y a une
solution que lorsqu'il n'y en a pas, car dans le
deuxième cas, vous risquez de tout explorer
avant d'aboutir à une conclusion d'inexitence. Seule
la logique mathématique (ou le bon sens si vous
voulez, mais après il faut se justifer) permet de tirer ce genre de
conclusion sans une quelconque exploration (mais pour y arriver, il faut sans doute réduire ses
distractions de beaucoup!. Si vous ne
trouvez rien, personne ne saura que c'est pour cette
raison que vous aviez l'air triste pendant
une période de votre vie, à vous de voir).
Notre cerveau va plus loin, il est par exemple capable de rechercher une information abstraite et indéfinissable, c'est ainsi lorsque vous essayez péniblement de retrouver le nom d'une personne tout en sachant comment elle ne s'appele pas (avec quoi comparez-vous alors pour dire « non ce n'est pas X » ? hein ?).
Deux conjectures trônent
en ce moment dans le monde la complexité,
celle qui affirme que les problèmes NP-complets sont
réellement difficiles, et celle qui affirme
que les questions d'existence et d'inexistence ne sont
pas quantitativement pareilles. Celui qui
élucidera l'une de ces questions pourra sans doute
fonder une réligion et avoir de sérieux
adeptes. Je lui conseillerai de faire son voeux de
pauvreté beaucoup plus tard, car un prix d'un
montant d'1 million de dollars a été mis en jeu par
the Clay Mathematics Institute à ce
sujet (quand je pense qu'il y a des gens qui
en gagnent autant juste en se prêtant au jeu d'un spot publicitaire).
Il
est clair que la question sous-jacente à propos de la NP-complétude est celle de la
dépendance à une énumération exhaustive. L'être humain aime bien répondre à une question d'existence par un exemple (d'où l'embarras lorsqu'il s'agit de la non existence, la tête qu'on fait dans ce cas là!!!). Il est des domaine où l'on dispose
de procédés efficaces pour trouver des solutions, pourtant l'espace de
recherche est infini. Le cas le plus connu est celui de l'optimisation
différentiable dans un espace dense (continu). Mon avis personnel est le suivant: dans le cas où on ne peut/sait pas construire une solution directe, alors on ne peut s'affranchir
d'une énumération exhaustive que s'il y a un lien logique et mécanique entre les solutions
potentielles. Il faut donc trouver ce lien, ou encore prouver qu'il n'en
existe pas, on n'y échappe vraiment pas!!!!
Liens intéressants / Interesting links