Informatique & IA · l'expérience
Bats la limite
Un réseau, un groupe de personnes qui se connaissent toutes, un raccourci de 1985 par la multiplication de matrices, et une hypothèse qui a tenu des décennies. Quatre questions, du débutant à l'expert, sur la fin de l'hypothèse k-Clique.
1 · Dis ce qui a été démontré
Débutant
Que montre l'article à propos de l'hypothèse k-Clique ?
2 · Calcule le coût de 1985
La méthode de Nešetřil et Poljak trouve une k-clique en environ n^(ωk/3) étapes. Prends k = 9 et ω = 2, la plus petite valeur que ω puisse avoir.
Intermédiaire
Quel exposant de n donne la méthode de 1985 ?
3 · Explique le « même si ω = 2 »
L'hypothèse prédit un coût de n^(ωk/3). La valeur exacte de ω est inconnue : elle vaut au moins 2, et l'article cite une borne supérieure de 9/4.
Expert
Pourquoi compte-t-il que le nouveau gain tienne quel que soit ω, même ω = 2 ?
4 · Reporte le gain
Max-2-CSP, qui comprend Max-Cut et Max-2-SAT, sur n variables booléennes, se résolvait en environ 2^(ωn/3) étapes. Répartis les variables en neuf groupes, et chaque affectation d'un groupe devient un sommet d'un problème de 9-clique pondéré.
Expert
Que donne le nouvel algorithme de cliques pour ces problèmes ?
Limite battue
—