Non, Candy Crush Saga n’est pas un jeu vidéo ridicule, c’est un problème NP-complet. Toby Walsh, de l’Université de Nouvelles-Galles du Sud (Australie), a publié en mars 2014 une étude démontrant que ce jeu s’apparente à la catégorie la plus complexe de “problèmes de décision”. Un problème de décision est une question mathématique dont la solution est soit oui soit non. La branche des maths appelée informatique théorique associe à la question posée un algorithme renvoyant une solution. Mais vue la difficulté des problèmes NP-complets, les algorithmes connus pour les résoudre sont inexploitables. Les 93 millions de personnes s’adonnant chaque jour à Candy Crush vont-elles permettre de surmonter cette difficulté ? Par exemple, si les chercheurs cachaient de vrais problèmes NP-complets dans le jeu ?

Source : Sciences pour tous