Pourquoi certains problèmes sont-ils plus compliqués que d’autres ? Et bien sûr, comment les résoudre ? Ça fait plus de 50 ans que les chercheurs en science du calcul par ordinateur travaillent sur ces questions. Comment rendre faciles et rapides les prédictions des tendances économiques ou les secrets du cosmos ? Grâce aux avancées en intelligence artificielle et en science des données, on trouve de nouvelles réponses à ces questions. Mais pour saisir toute la portée de ces technologies, il est essentiel de comprendre certains concepts fondamentaux, comme les problèmes P et NP. Ce sont ces problèmes qui définissent les limites de ce que nos outils les plus avancés peuvent réaliser.

D’abord, les bases : problèmes P et NP : au cœur de la théorie de la complexité, deux classifications dominent : P et NP. Les problèmes de type P sont ceux pour lesquels les solutions peuvent être trouvées rapidement par des algorithmes, croissant polynomialement avec la taille des données. Imaginez-les comme des puzzles que l’on peut résoudre en un temps raisonnable. En revanche, les problèmes NP sont plus taquins : chaque solution potentielle peut être vérifiée rapidement, mais trouver cette solution peut être l’œuvre de toute une vie (respect à tous les chercheurs qui travaillent sur les 6 problèmes du millénaire restant). Un problème P c’est typiquement trier une liste, rechercher un numéro de téléphone dans un annuaire ou encore trouver le chemin le plus court entre un point A et un point B.  Un problème NP, c’est plutôt faire un plan de table pour un mariage (c’est facile de vérifier que l’organisation finale est la bonne, mais pour y arriver il a fallu un peu de boulot ^^), c’est aussi gérer un planning d’équipe dans un service d’hôpital, ou encore trouver la bonne organisation pour déménager ses affaires en un minimum de trajet.

L’IA apporte de nouvelles solutions : prenons l’exemple de la reconnaissance faciale. D’un point de vue numérique, cela relevait des problèmes NP infranchissables à cause de la variabilité des conditions d’imagerie, de la diversité des populations, ou encore du besoin d’avoir la réponse en temps réel ! Et bien grâce aux réseaux de neurones, à des jeux de données diversifiés, à la parallélisation des calculs, ou encore aux transferts d’apprentissage, c’est devenu possible.

Des défis encore plus énormes à résoudre : cependant, transformer un problème NP en P reste une quête idéale, et le travail quotidien de beaucoup de DataScientist. Si cela était toujours possible, si on trouvait un système pour rendre n’importe quel problème NP en problème P, cela signifierait une révolution de pensée. Ça reviendrait tout simplement à redéfinir les limites de notre capacité à résoudre un problème. À titre personnel, et de manière purement expérimentale, je me suis tourné vers l’analyse des dimensions d’un problème et de sa solution (ici, dimension = nombre de paramètres). Quand vous avez un problème à X dimensions, j’ai constaté qu’il existait souvent une solution à X+1 dimensions. Quand vous êtes prisonnier d’un enclos (un problème à 2 dimensions) vous pouvez sauter par-dessus pour en sortir (utilisation d’une 3eme dimension).

Intégrer l’IA dans nos pratiques n’est pas simplement une évolution ; c’est aussi un moyen de franchir un dôme de verre des problèmes considérés jusque-là impossibles. Ça redéfinit les fondamentaux de la résolution de problèmes et par conséquent la nature des défis que nous choisissons de relever. Encourageons donc tous les chercheurs et scientifiques que nous connaissons à non seulement envisager comment l’IA peut être employée, mais aussi comment elle doit être conçue, pour construire des solutions qui nous impactent tous positivement.

Vous avez un problème NP ? partagez le !

Gilles

Des exemples d’IA appliqués à des problèmes NP :

• L’optimisation des flottes de véhicules et des livraisons multiemplacement
• Prédire la structure de protéines à partir d’acides aminés
• Trouver les failles des systèmes de cryptage
• Outils de planification et d’équipes
• Optimisation d’un portefeuille financier pour maximiser les gains tout en minimisant les risques

Des laboratoires à interroger :

• L’INRIA
• LIP6
• LMB (Laboratoire de Mathématiques de Besançon)