Décrypter le code de la complexité dans le problème informatique P vs NP
De nouvelles recherches de l’Université de Waterloo permettent de résoudre l’un des plus gros problèmes de l’informatique théorique. Mais la façon de le faire, selon Cameron Seth, titulaire d'un doctorat. chercheur travaillant dans le domaine de l'approximation algorithmique, consiste à décomposer le problème en morceaux plus petits.
« Tous ceux qui travaillent en informatique et en mathématiques connaissent le problème » P contre NP « », explique Seth. « C'est l'un des problèmes notoires du Prix du Millénaire : si célèbre et si difficile que le résoudre vous rapportera un million de dollars. »
Pour comprendre le nœud du problème « P contre NP », imaginez un énorme puzzle ou un puzzle Sudoku. Ce serait un problème « P » s'il pouvait être résolu relativement rapidement par un ordinateur, alors qu'il s'agirait d'un problème « NP » s'il était extrêmement difficile à résoudre, mais qu'une solution fournie pourrait être rapidement vérifiée.
Par exemple, une grille de Sudoku peut prendre beaucoup de temps à résoudre (peut-être des heures), mais une fois la solution fournie, il ne faut que quelques secondes pour vérifier que toutes les colonnes et toutes les lignes comportent les bons chiffres.
« Avec P vs NP, la question qui empêche tout le monde de dormir la nuit est de savoir si chaque solution qui peut être vérifiée rapidement est également un problème qui peut être résolu rapidement. Tout problème facile à vérifier est-il également facile à résoudre ? »
Les implications pratiques de cette question persistante en informatique affectent d’importantes recherches et développements dans les domaines de la cryptographie, de l’IA et de l’optimisation. Les méthodes de chiffrement les plus couramment utilisées pour les réseaux sensibles de toutes sortes reposent sur l’hypothèse qu’il existe des problèmes extrêmement difficiles à résoudre mais faciles à vérifier. C'est la logique sous-jacente à tout, des mots de passe en ligne aux virements bancaires sécurisés.
Plutôt que d'aborder le problème de front, les recherches de Seth recherchent plutôt des solutions à des problèmes approximatifs.
« Ce que je fais, c'est examiner une série de problèmes plus petits liés au problème plus large P vs NP. Essentiellement, ce que je demande, c'est si nous pouvons résoudre ces autres problèmes connexes », explique Seth.
Ses récentes recherches sur les algorithmes graphiques, par exemple, imaginent un immense réseau avec un nombre énorme de connexions, comme on pourrait en trouver dans une immense application de réseautage social en ligne. Seth découpe une plus petite partie du réseau graphique et se demande ce que cette plus petite pièce du puzzle peut nous apprendre sur l'ensemble.
Cette innovation technique fournit un outil combinatoire qui peut ensuite aider à résoudre des problèmes d'optimisation complexes. De tels outils réduisent un très grand nombre de combinaisons possibles à un sous-ensemble gérable. Les recherches fondamentales de Seth visent, en ce sens, à résoudre ces problèmes bien plus redoutables pour l’informatique.
« Ce que je fais dans mes recherches ne consiste pas exactement à trouver une solution unique, mais à décider s'il existe une solution proche et ce que cela pourrait nous apprendre sur l'ensemble de problèmes similaires. »
L'article, « A Tolerant Independent Set Tester », a été présenté lors du Symposium 2025 sur la théorie de l'informatique. Les résultats sont publiés sur le arXiv serveur de préimpression.
