Lors du Vienna Summer of Logic a eu lieu une discussion au sujet de la théorie et de la pratique du test de satisfiabilité propositionnelle (SAT-solving). Au delà de ses aspects purement technique, cette discussion soulevait d'intéressantes questions épistémologiques.

La satisfiabilité propositionnelle est un problème dont la résolution efficace est de première importance pour l'industrie électronique. En effet, les problèmes de vérification de la bonne conception des circuits intégrés numériques peuvent souvent être ramenés à un problème de satisfiabilité propositionnelle. Il y a donc une motivation forte à développer des approches efficaces en pratique.

Par ailleurs, la satisfiabilité propositionnelle est un problème difficile, au sens que les programmes informatiques qui le résolvent, même s'ils sont rapides dans de nombreux cas, ont toujours une catégorie de cas où ils sont intolérablement lents. Plus précisément, le temps de calcul des programmes, dans le pire cas, croît exponentiellement avec la taille du problème à résoudre : quand on accroît d'une unité la taille du problème, on double le temps de calcul.

Dès les années 1950, on a distingué deux sortes de problèmes informatiques : ceux pour lesquels on trouvait des méthodes (on dit : des algorithmes) raisonnablement rapides, et ceux qui, dans le pire cas, nécessitent une exploration exhaustive d'un espace de recherche de taille exponentielle et donc un temps de calcul exponentiel. Ainsi, pour trier une table de n nombres, on trouve sans peine un algorithme dont le temps de calcul est quadratique, c'est-à-dire qu'il quadruple quand n est doublé : il suffit de chercher le nombre le plus petit dans la table, le mettre en tête, et trier le reste du tableau. Avec un peu plus d'astuce, on peut trouver des méthodes de complexité quasi linéaire, qui se contentent de faire un peu plus que doubler le temps de calcul quand le nombre de données à trier double (de fait, de telles méthodes sont à l'œuvre dans tous les systèmes qui ont à trier des données). En revanche, pour le test de satisfiabilité propositionnelle, on se retrouvait toujours dans le pire cas à explorer un nombre exponentiel de combinaisons. Ces caractéristiques ne dépendent pas du matériel utilisé pour calculer, raison pour laquelle ce qui a été constaté dans les années 1950 reste d'actualité alors que la technologie du calcul a fait des progrès considérables.

Dans les années 1970, on a développé la théorie de la complexité algorithmique. Cette théorie distingue notamment les problèmes de complexité polynomiale (il existe une définition précise de ce terme, que je ne donnerai pas ici : disons simplement que les problèmes quasi-linéaires et quadratiques sont polynomiaux) des autres. Parmi ces autres, on distingue ceux qui reviennent à explorer un espace de taille exponentielle (ou du moins exponentielle de polynôme, mais ne compliquons pas) à la recherche d'une solution (là encore, une définition mathématique précise existe). Les premiers forment la classe P, les seconds la classe NP, la première étant incluse dans la seconde. La question de savoir s'il P et NP sont distinctes, ou en termes intuitifs (et un peu trompeurs, comme nous allons le voir) s'il existe des problèmes qu'on ne peut résoudre substantiellement mieux que par une exploration exhaustive d'un nombre exponentiel de combinaisons, est une des grandes questions des mathématiques du tournant du millénaire : bien que l'on conjecture que ces classes sont distinctes et notamment que le test de satisfiabilité booléenne soit un de ces problèmes, on n'en a pas la preuve.

Un aspect important de la théorie de la complexité est qu'elle considère les problèmes que l'on compte résoudre et non telle ou telle méthode de résolution. Autrement dit, si un problème est de haute complexité, c'est une caractéristique intrinsèque et non due à la faiblesse des algorithmes découverts jusqu'à présent. Alors qu'en médecine on peut espérer trouver un moyen de soigner une maladie jusque là incurable, une vérité mathématique reste vraie…

La théorie de la complexité souffre toutefois de faiblesses. Nous avons déjà évoqué le fait que certaines grandes conjectures de cette théorie (par exemple, P≠NP) restent non démontrées ; parlons maintenant du péril qu'il y a à relier une notion de complexité théorique avec une notion pratique, comme la difficulté effective de résolution d'un problème.

Il est courant que les chercheurs en informatique démontrent qu'un problème est « NP-complet » (un des problèmes « les plus difficiles » de la classe NP, avec une définition mathématique précise) ; ils en déduisent que, sous réserve de la conjecture P≠NP, il n'existe pas pour ce problème d'algorithme de complexité polynomial et concluent souvent à l'absence d'algorithme efficace. Or, pareille conclusion, identifiant faisabilité pratique et existence d'un algorithme polynomial, est franchement discutable. Un algorithme de complexité polynomiale de degré élevé (par exemple, où le temps de résolution du problème serait multiplié par un milliard à chaque fois que la taille du problème du problème d'entrée doublerait) serait inutilisable ; en revanche, un algorithme de complexité exponentielle dans le pire cas peut être utilisable si ce pire cas n'arrive pas en pratique (ceci s'entend : hors exemples artificiels conçus spécialement pour exhiber ce pire cas).

Autrement dit, nous avons une théorie parfaitement correcte, mais dont il est délicat de dériver des indications sur ce qu'il convient ou non de faire. Ainsi, on résout quotidiennement dans l'industrie, notamment dans la conception et vérification de circuits intégrés, des problèmes NP-complets (SAT, « voyageur de commerce »...), parce qu'on a des méthodes qui fonctionnent en pratique sur les cas qui nous intéressent ; il aurait été dommage de s'en tenir à remarquer que le problème est NP-complet et abandonner tout espoir. Un autre exemple : la sécurité informatique : on peut argumenter qu'un système de chiffrement est sûr parce que le casser implique de résoudre un problème NP-complet, mais cet argument est-il valable alors que ce qui est important en sécurité n'est pas que le système soit difficile à casser dans le pire cas pour l'adversaire, c'est-à-dire dans le meilleur cas pour nous, mais plutôt qu'il soit difficile à casser dans les cas favorables pour l'adversaire ?

Puisqu'il est périlleux de ne se référer qu'au cas le pire, on a voulu étudier le « cas typique » et pour cela considérer le « cas moyen », au sens des probabilités. Ceci présuppose une distribution de probabilité, autrement dit d'une répartition des cas de figure que l'on étudie et de leur probabilités respectives ; on espère que les cas les pires sont très peu probables. Malheureusement, sur le problème SAT, les distributions de probabilité les plus « simples » et fortement étudiées ne sont absolument pas représentatives des cas industriels réels ! Un autre exemple : l'algorithme classique du « tri rapide » a une fort bonne complexité moyenne, sauf que son cas le pire est atteint dans un cas « rare » au sens des probabilités, mais assez courant en pratique : quand une partie de données sont déjà triées !

Peut-être faut-il (temporairement ?) abandonner l'espoir de résultats théoriques forts et s'en tenir à une évaluation empirique, où l'on essaye les différentes approches sur des « cas représentatifs » ? Hélas, se pose alors la question de ce qui est ou non représentatif, et des conséquences du choix d'une bibliothèque de « cas représentatifs » sur le domaine de recherche.

Qu'est-ce qu'un « cas représentatif » ? On distingue habituellement :

  1. Des exemples artificiels générés pour illustrer telle ou telle difficulté faisant souffrir telle ou telle catégorie d'algorithmes. (Par exemple, sur SAT, on génère des « problèmes de pigeons ».)

  2. Des exemples rédigés à la main pour illustrer telle ou telle difficulté faisant souffrir telle ou telle catégorie d'algorithmes et, souvent, pour illustrer la supériorité de telle ou telle approche (il circule ainsi dans la littérature scientifique, parfois à mon grand étonnement,des exemples « David », « Monniaux » ou « Halbwachs », extraits d'articles ou de questions posées en ligne par moi-même ou le directeur de mon laboratoire).

  3. Des exemples industriels.

Première difficulté : les catégories 1 et 2 ne sont pas forcément représentatives de vrais problèmes se posant industriellement. Il y a donc le risque de dépenser du temps et de l'énergie en recherches visant à améliorer les performances sur des cas artificiels et sans véritable intérêt.

Deuxième difficulté : les exemples industriels ne représentent pas forcément tout ce que l'on pourrait vouloir résoudre. Pour convertir un problème industriel concret en un problème prêt à être résolu par un outil SAT ou un outil d'optimisation, il faut un certain effort ; typiquement il faut développer un logiciel de conversion, voire une interface utilisateur, peut-être développer une base de données. Pour prendre un exemple de la vie courante, dans un GPS de voiture, l'algorithme de calcul de plus court chemin n'est qu'une toute petite partie du dispositif, qui nécessite une énorme base de donnée, un dispositif de visualisation, un dispositif pour rentrer la demande de l'utilisateur… Il faut donc investir avant même de s'attacher à la résolution proprement dite des « problèmes industriels » ; or un industriel sera réticent à cet investissement s'il n'est pas sûr que les méthodes de résolution derrière pourront suivre. Ceci biaise la base des exemples industriels dans le sens de ce que l'on sait déjà résoudre, ou du moins dans le sens d'exemples ressemblant à ceux que l'on sait déjà résoudre (par exemple, que l'on peut obtenir en convertissant des exemples plus gros que ceux que l'on sait gérer actuellement).

Enfin, l'évaluation des outils par des compétitions sur les bases d'exemples standardisés, si elle favorise une certaine émulation, peut inciter au conformisme, à des améliorations incrémentales qui occupent les chercheurs et font publier des articles, mais ne changent rien de bien profond.

En résumé, nous avons

  • une théorie très ardue, mais qui déjà a du mal à conclure à l'intérieur d'elle-même, et dont il est parfois délicat de tirer des conséquences pratiques

  • une évaluation expérimentale délicate et biaisée.

Je me demande ce qu'il en est dans les autres domaines de recherche. Le premier exemple qui me vient à l'esprit est l'économie : on y trouve d'admirables modèles théoriques (par exemple, les équilibres de Nash) sur lesquels on peut rédiger quantité d'articles, mais pour lesquels se pose le problème de la représentativité par rapport aux situations réelles — problème d'autant plus grave si l'on prétend tirer du modèle des recommandations politiques.