NP-complétude vue par Claude Tadonki

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!!!!