En informatique, le problème de coloration de graphe est un classique. Inspiré par le problème de la coloration des cartes, il demande :Étant donné un réseau de nœuds reliés par des liens, quel est le nombre minimum de couleurs dont vous avez besoin pour colorer chaque nœud afin qu'aucun lien ne relie deux de la même couleur ? Pour un petit nombre de couleurs et de liens, la recherche d'une solution est simple :essayez simplement toutes les combinaisons possibles. Mais à mesure que les liens augmentent, le problème devient plus limité - jusqu'à ce que, s'il y a trop de liens et pas assez de couleurs, aucune solution ne peut exister du tout.

"Ensuite, il y a ces zones intermédiaires fascinantes où il y a probablement une solution, mais c'est très difficile à trouver—et un autre où il n'y en a probablement pas, mais il est difficile de prouver qu'il n'y en a pas, " dit le mathématicien Cris Moore, professeur résident à la SFI. Cela signifie que les algorithmes conventionnels de résolution de problèmes ne peuvent pas les trouver, il dit. Si l'on part d'une coloration aléatoire, par exemple, et commence juste à inverser les couleurs des nœuds, il ne trouvera pas l'une de ces solutions cachées.

Dans un nouvel article présenté à la Conférence 2021 sur la théorie de l'apprentissage, Moore et ses collaborateurs décrivent une nouvelle façon de construire des problèmes avec de telles solutions cachées. Le groupe comprend le mathématicien Jess Banks, un ancien stagiaire de premier cycle et post-bac SFI qui poursuit actuellement un doctorat. à l'Université de Californie-Berkeley.

Ils abordent le problème en se faisant une sorte d'avocat du diable mathématique. Au lieu de résoudre des problèmes, ils forment du neuf, complexes, avec des solutions cachées à l'intérieur. "On enlève le chapeau blanc du solveur, le chercheur de solutions, et nous mettons le chapeau noir de la personne qui conçoit des problèmes délicats - presque comme la cryptographie, " dit Moore. " La solution est cachée. "

Les chercheurs ont conçu une manière subtile de cacher des solutions, dit Moore. Et quand ils confient ces problèmes à des algorithmes de résolution de problèmes, les algorithmes sont vides. "Si nous pouvons créer des problèmes que beaucoup d'algorithmes ne peuvent pas résoudre, ou même dire s'il y a une solution, " dit Moore, "alors nous avons des preuves solides que nous avons localisé la zone où ces problèmes sont difficiles."

L'article comprend un théorème prouvant que plusieurs familles d'algorithmes ne parviennent pas à trouver des solutions à ces problèmes générés. Cela signifie que les chercheurs sont plus proches que jamais d'identifier la limite de transition de phase de cette zone "dure" dans laquelle il est difficile de trouver des solutions - ou de prouver qu'il n'y en a pas.

Moore dit que l'effort continu pour identifier avec précision les problèmes est né de conjectures en physique qui demandent comment les systèmes changent à mesure qu'ils deviennent plus contraints.

"Notre aventure, " il dit, « a été de transformer ces conjectures et calculs de physique en preuves mathématiques ». Et la seule façon de continuer à pousser le champ vers l'avant, il dit, est de faire appel aux forces croisées des outils mathématiques, la physique, et informatique.