QUAND UN 1 COÛTE PLUS QU'UN 0, COMPRESSER DEVIENT DIFFICILE

Pour stocker ou envoyer un texte de façon compacte, on donne à chaque symbole un mot fait de 0 et de 1, court pour les symboles fréquents et plus long pour les rares. Les mots doivent former un code préfixe : aucun mot ne peut être le début d’un autre. {0, 10, 11} convient ; {0, 01, 11} non, puisque 0 commence 01. Avec un code préfixe, une longue suite de bits se redécoupe en mots sans aucun séparateur.

Le meilleur code de ce type — celui dont la longueur moyenne est la plus petite — a été trouvé en 1952 par D. A. Huffman, avec une recette gloutonne simple — qui fait à chaque étape le choix le plus avantageux sur le moment — et qui s’exécute vite.

Quand les lettres ont un prix

La recette de Huffman suppose qu’un 0 et un 1 coûtent pareil. Supposons que non : le 1 met plus de temps à transmettre, ou prend plus de place à stocker. Chaque mot coûte alors la somme de ses lettres, et la composition d’un mot compte autant que sa longueur. Avec des coûts 1 et 3, par exemple, 00 et 01 ont la même longueur mais coûtent 2 et 4.

Cette variante a une longue histoire. R. M. Karp l’a écrite en 1961 comme un problème de programmation en nombres entiers — une optimisation dont les inconnues doivent être des nombres entiers. Des travaux ultérieurs ont trouvé des algorithmes exacts et efficaces pour chaque couple fixé de coûts entiers, et une méthode d’approximation qui s’approche de l’optimum autant qu’on le souhaite. Mais quand les coûts eux-mêmes font partie des données, personne ne savait à quel point le problème était difficile. En 2021 encore, la question figurait parmi les problèmes ouverts.

La réponse : NP-complet

L. Sunil Chandran, de l’Indian Institute of Science à Bengaluru, et Rishikesh Gajjala, de Pramaana Labs, prouvent aujourd’hui que décider s’il existe un code de coût au plus K est NP-complet — même quand les deux coûts sont des entiers consécutifs, M et M + 1. Les informaticiens disent qu’un problème est NP-complet quand il est aussi difficile que toute une famille de problèmes classiques : une méthode rapide et générale pour l’un en donnerait une pour tous, et on n’en connaît aucune. Trouver le code le moins cher, qui répondrait aussitôt à cette question par oui ou par non, est donc au moins aussi difficile — NP-difficile, dans le jargon.

Aucune contradiction avec les algorithmes rapides pour des coûts fixés. Dans la preuve, M grandit avec les données ; pour tout couple de coûts fixé à l’avance, ces algorithmes restent valables.

Une énigme cachée dans un arbre de codage

La preuve part d’un problème difficile connu : dans un réseau dessiné sur une feuille sans croisement, peut-on choisir k points dont aucun couple n’est relié ? Elle construit ensuite un problème de codage dont le code le moins cher répond à cette question.

1. Tout code préfixe est un arbre : 0 va à gauche, 1 à droite, et chaque mot est une feuille, le bout d’une branche. Un mot de profondeur d — c’est-à-dire de d lettres — contenant z fois la lettre 1 coûte M × d + z quand les lettres coûtent M et M + 1. La profondeur fixe la grosse part du coût, le nombre de 1 la petite.
2. Les auteurs conçoivent un nouveau problème intermédiaire : fixer combien de feuilles l’arbre a à chaque profondeur, et noter l’emplacement de ses feuilles. Ils montrent qu’un arbre bon marché doit, en grandissant niveau par niveau, exécuter un petit programme qui examine les points choisis un à un, recopie chaque choix et teste chaque lien. Tout écart à ce programme coûte au moins une unité de plus ; chaque point choisi en fait gagner exactement une.
3. Enfin, les fréquences sont réglées pour forcer chaque symbole à la bonne profondeur, et le score devient le coût du code plus une quantité fixe.

Un petit exemple de l’article montre à quel point les coûts sont subtils. Trois symboles ont pour fréquences 20, 12 et 9 ; le 0 coûte 83 et le 1 coûte 84. Le code (0, 10, 11) — 0 pour le symbole le plus fréquent, 10 et 11 pour les deux autres — coûte 5 176. Le code (1, 00, 01) coûte 5 175 : donner la lettre chère au symbole le plus fréquent est gagnant, car les deux autres mots portent alors moins de 1.

Où se cache la difficulté

Un second résultat situe le problème au cœur du codage ordinaire. La recette de Huffman trouve vite la longueur moyenne la plus courte. Mais parmi tous les codes qui atteignent cette longueur, choisir celui qui a le moins de 1, pondérés par la fréquence, est lui aussi NP-complet.

Des questions restent ouvertes : le problème reste-t-il difficile quand tous les nombres sont petits (la NP-difficulté dite forte), et existe-t-il une méthode rapide qui approche l’optimum à toute précision, avec un temps de calcul qui croît aussi raisonnablement avec cette précision ?

Une preuve trouvée avec une IA

L’article dit comment il a été obtenu. Les auteurs ont d’abord demandé à Codex, d’OpenAI, une preuve de difficulté pour un problème plus général, puis de l’étendre aux codes non binaires et enfin aux codes binaires. Codex a contribué à la stratégie de la réduction (la traduction de l’énigme sur les réseaux en problème de codage) et à son développement mathématique ; il a aussi aidé à la rédaction, à la vérification des arguments et à la construction d’exemples. Les auteurs ont guidé le travail, demandé corrections et simplifications, largement réécrit l’exposé, et assument la responsabilité des énoncés et des preuves. Comme toute prépublication, elle n’a pas encore été relue par des pairs.