Quel serait selon vous le problème mathématique le plus important du siècle ? Beaucoup d’experts du domaine répondraient « la conjecture P vs NP ! ».
Entre les mathématiques et l’informatique théorique, cette question traite de la notion d’algorithme, c’est à dire de notre manière de décrire un processus, un calcul, et les différentes étapes qui le composent. Que peut-on dire du temps nécessaire pour résoudre un problème ? Peut-on deviner s’il va nous résister longtemps ? Maîtriser ces questions fait partie des bases de la cryptographie moderne et des systèmes de sécurité utilisés dans le monde entier.
La conjecture P vs NP y joue un rôle décisif, elle nous oriente vers une vérité étonnante : les problèmes semblent se séparer en deux classes, caricaturalement ceux qu’on peut estimer « faciles à résoudre » et les autres, plus persistants. Cette séparation représente-t-elle réellement une vérité fondamentale ? Ou est-ce au contraire une illusion ?
Plongez avec nous au cœur de cette conjecture et de ses subtilités ! Peut-être remporterez-vous le million de dollars que l’Institut de mathématiques Clay se propose d’offrir depuis presque 20 ans, à quiconque en viendra à bout ?