Imaginez que vous êtes un voleur qui vole une exposition de Musée de bijoux alléchants, de géodes et de gemmes rares. Vous êtes nouveau dans ce domaine, donc vous n’avez apporté qu’un seul sac à dos. Votre objectif devrait être de vous en tirer avec les objets les plus précieux sans surcharger votre sac jusqu’à ce qu’il se casse ou devienne trop lourd à transporter. Comment choisissez – vous parmi les objets pour maximiser votre butin? Vous pouvez lister tous les artefacts et leurs poids pour élaborer la réponse à la main., Mais plus il y a d’objets, plus ce calcul devient taxant pour une personne—ou un ordinateur.
ce dilemme fictif, le « problème du sac à dos”, appartient à une classe de problèmes mathématiques célèbres pour repousser les limites de l’informatique. Et le problème du sac à dos est plus qu’une expérience de pensée. « Beaucoup de problèmes auxquels nous sommes confrontés dans la vie, que ce soit les affaires, la finance, y compris la logistique, le chargement des porte — conteneurs, le chargement des avions-ce sont tous des problèmes de sac à dos”, explique Carsten Murawski, professeur à L’Université de Melbourne en Australie., « D’un point de vue pratique, le problème du sac à dos est omniprésent dans la vie quotidienne. »
Les chercheurs ont autrefois profité de la complexité du problème pour créer des systèmes de sécurité informatique, mais ceux-ci peuvent maintenant être fissurés car le problème a été si bien étudié. Aujourd’hui, alors que la technologie capable de briser les verrous de nos communications numériques se profile à l’horizon, le problème du sac à dos pourrait inspirer de nouvelles façons de se préparer à cette révolution.
tout ou rien
le problème du sac à dos appartient à une classe de problèmes « NP”, qui signifie « temps polynomial non déterministe.,” Le nom fait référence à la façon dont ces problèmes forcent un ordinateur à passer par de nombreuses étapes pour parvenir à une solution, et le nombre augmente considérablement en fonction de la taille des entrées—par exemple, l’inventaire des articles à choisir lors du remplissage d’un sac à dos particulier. Par définition, les problèmes NP ont également des solutions faciles à vérifier (il serait trivial de vérifier qu’une liste particulière d’éléments tient, en fait, dans un sac à dos).,
« le problème que les théoriciens ont commencé à examiner était l’efficacité avec laquelle une tâche particulière peut être effectuée sur un ordinateur”, écrit Keith Devlin dans le livre The Millennium Problems. Par exemple: étant donné une liste de 1 million d’artefacts de musée avec leurs poids et leurs valeurs monétaires, et un sac à dos limité à 25 livres, un ordinateur devrait parcourir toutes les combinaisons possibles pour générer le seul avec le transport le plus lucratif. Étant donné un laps de temps indéfini, un ordinateur pourrait utiliser la force brute pour optimiser de gros cas comme celui-ci, mais pas sur des échelles de temps qui seraient pratiques.,
« nous pensons que vous pourriez couvrir toute la Terre avec des processeurs et les exécuter jusqu’à la mort par la chaleur de l’univers et ne parviennent toujours pas à résoudre des cas relativement petits de versions appropriées de ces problèmes”, explique Noah Stephens-Davidowitz, chercheur Microsoft au Simons Institute à Berkeley, en Californie.
certains problèmes NP comme l’exemple du sac à dos ont une propriété spéciale: au début des années 1970, Stephen Cook et Richard Karp ont montré qu’une variété de problèmes NP pouvaient être convertis en un seul problème de logique formelle., Par conséquent, si l’on pouvait être résolu et vérifié efficacement avec un algorithme, ils le pourraient tous. Cette propriété est connue sous le nom de « complétude NP. »
l’une des questions les plus tenaces en informatique et en mathématiques est de savoir si ces problèmes « NP”, y compris le problème du sac à dos, sont vraiment différents des problèmes « P”, ceux qui peuvent être résolus en ce qu’on appelle le temps polynomial. SI P=NP, alors il est possible de résoudre tous les problèmes dont les solutions sont faciles à vérifier, dit Stephens-Davidowitz. Donc, si cette inégalité persiste, Le Problème général du sac à dos sera toujours difficile.,
garder les choses secrètes
Les chercheurs en cryptographie adorent les problèmes difficiles à résoudre pour les ordinateurs car ils sont utiles pour crypter les messages numériques. Les codes de sécurité de type knapsack-problem ne sont pas utiles pour cela, car ils sont trop facilement fissurés, mais des méthodes plus compliquées inspirées par ce problème sont en cours de développement et pourraient un jour jouer un rôle pour déjouer la prochaine génération d’informatique.,
dans une première méthode de chiffrement de type sac à dos, la clé privée d’une personne serait une liste de nombres dans lesquels chacun est plus grand que la somme de ses prédécesseurs. Les échanges impliquant cette personne utiliseraient une clé publique qui semble aléatoire mais qui est composée de nombres de la première liste avec des transformations spécifiques appliquées. Par exemple, si la clé publique est , le message transmis « 1, 0, 0, 1” sera codé comme 2+0+0+5 = 7 (parce que 2*1=2, 3*0=0, 4*0=0, et 5*1=5). Les numéros secrets impliqués dans les conversions entre les clés permettent de dévoiler le message d’origine.,
Pour que cela fonctionne, l’ordinateur doit également déterminer si un nombre donné peut être écrit comme la somme d’un sous-ensemble de nombres dans la clé privée, qui devient un simple problème de sac-à-dos. C’est comme remplir un sac à dos avec un lot d’objets de tailles différentes — comme une bague, une peinture, une voiture et une maison — et savoir que vous ne pouvez pas remplir autre chose après avoir vérifié que l’anneau et la peinture correspondent. Les cryptographes Ralph Merkle et Martin Hellman ont décrit cette idée en 1978, mais d’autres ont compris comment la casser au début des années 1980.,
Les échanges D’informations privées sur internet d’aujourd’hui utilisent souvent des clés impliquant de grands nombres premiers, et bien que l’affacturage de grands nombres soit difficile, on ne pense pas qu’il appartienne à la même classe « NP complète” que le problème du sac à dos. Cependant, les informaticiens se préparent déjà à un avenir dans lequel les ordinateurs quantiques peuvent rapidement déverrouiller ces clés.
les ordinateurs quantiques reposent sur les principes de la mécanique quantique, qui dit qu’une particule n’est pas située dans une seule position mais a une probabilité d’être dans de nombreux endroits différents à moins qu’elle ne soit épinglée et mesurée., Alors que les ordinateurs normaux encodent des informations en 0s et 1s, chaque « qubit » dans un ordinateur quantique aurait un large éventail d’états possibles liés aux propriétés des particules. Les ordinateurs quantiques ne seraient pas utiles pour naviguer sur internet ou écrire un scénario dans un café, mais ils libéreraient une puissance jamais vue sur quelques types de problèmes mathématiques. Malheureusement, ces problèmes mathématiques constituent les fondements de la cybersécurité moderne.
« dans un certain sens, nous avons eu vraiment de la malchance”, dit Stephens-Davidowitz., « Nous avons réussi à reposer la sécurité d’internet sur la dureté de certains des très rares problèmes qui semblent être difficiles pour les ordinateurs classiques mais faciles pour les ordinateurs quantiques. »
alors que l’informatique quantique en est à ses balbutiements, certains chercheurs disent que nous sommes en retard dans la préparation. En 2016, Le National Institute of Standards and Technology (NIST) a appelé à de nouvelles méthodes de cryptage résistant aux quantiques, annonçant 26 demi-finalistes l’année dernière. Un tel type d’algorithme en cours de développement est appelé cryptographie basée sur le réseau., Au lieu d’utiliser des nombres, il utilise des clés qui existent dans de multiples dimensions et impliquent la formation d’une structure en treillis faite de points également espacés dans l’espace. La question Est de savoir où sont ces points et à quel point un point aléatoire donné est proche des coordonnées d’un réseau. En son cœur, il s’agit d’un problème de sac à dos dans plus d’une dimension.
« mon obsession actuelle est d’essayer de comprendre à quel point ces choses basées sur le réseau sont sécurisées, idéalement avant de les utiliser pour faire fonctionner internet”, explique Stephens-Davidowitz.,
« cela signifie que nous avons besoin d’une cryptographie quantique beaucoup plus tôt que prévu pour que l’ordinateur quantique atteigne son plein potentiel”, a déclaré Leo Ducas, chercheur au Centrum Wiskunde& Informatica aux Pays-Bas.
Au-delà de la recherche en cryptographie, le problème du sac à dos et ses cousins NP complets sont partout dans la vraie vie. Par exemple, vous avez peut-être entendu parler du problème du « vendeur itinérant”, qui est également NP complet., Le défi ici est de trouver l’itinéraire le plus court pour un vendeur de voyager entre un nombre donné de villes avant de revenir au point de départ. Le problème de l’acheminement des véhicules, qui prend en compte plusieurs véhicules effectuant des livraisons, est étroitement lié.
Luciana Buriol, professeure agrégée à L’Universidade Federal do Rio Grande do Sul au Brésil, s’est attaquée à ce problème pour tenter de trouver de nouvelles approches pour le secteur des soins de santé., Elle a travaillé avec un service de soins à domicile où les médecins et les infirmières visitent les patients à domicile et les aident à optimiser leurs itinéraires, étant donné le nombre limité de voitures disponibles pour le transport.
« étant donné 300 patients et 15 voitures, vous ne pouvez pas trouver la solution dans un délai raisonnable”, a-t-elle déclaré. « Si vous avez des jours pour exécuter l’algorithme, vous trouverez — mais vous devez trouver en moins de 2 heures, sinon vous ne l’utiliserez jamais dans la pratique. »
aucun algorithme unique ne peut résoudre ces problèmes., Au lieu de cela, Buriol trouve des moyens rapides d’arriver à des approximations utiles afin qu’elles puissent être mises en action.
Des Sacs À Dos tout autour de nous
pour ceux d’entre nous qui ne sont pas informaticiens et qui sont confrontés à ce genre de problèmes dans la vie réelle, à quel point sommes-nous bons? Le groupe de Murawski trouve des résultats préliminaires que lorsque vous donnez aux humains des problèmes comme un sac à dos, nous luttons aussi puissamment., Dans de petites expériences où les participants ont été invités à remplir un sac à dos sur un écran d’ordinateur avec des articles portant des valeurs et des poids déclarés, les gens avaient tendance à avoir plus de mal à optimiser le contenu du sac à dos à mesure que le nombre d’options d’articles augmentait—le même problème que les ordinateurs. Les chercheurs disent que cette découverte peut être liée à la « surcharge de choix”: la façon dont nous gelons lorsque nous avons trop de choix, même dans des situations simples comme l’achat de confiture dans une épicerie.
Pourtant, dans le monde réel, nous vous en tirer. Faire attention est également un problème de sac à dos., Lorsque vous conduisez, nous sommes confrontés à une corne d’abondance de distractions possibles telles que les oiseaux, les nuages, la radio et les bâtiments environnants. Nous ne devons mettre que les stimuli les plus pertinents dans nos sacs à dos mentaux—et généralement, nous le faisons.
la question demeure: étant donné que les problèmes NP complets sont plus difficiles pour les ordinateurs que d’autres types d’énigmes, sont-ils également plus difficiles pour les gens? Les résultats initiaux limités suggèrent qu’ils pourraient l’être, ce qui a surpris Murawski.,
« si cela s’avère être le cas, cela suggérerait que la dureté de tels problèmes est une caractéristique des problèmes—une propriété de la nature—et non dans l’œil du spectateur”, dit Murawski.