Bonsoir,
Voici juste une petite nouvelle reliée au cours ICC (mais rassurez-vous, rien qui soit matière à examen!):
Les problèmes NP-complets, dont j'ai brièvement parlé au cours, sont les plus difficiles à résoudre de la classe NP. Parmi ceux-ci, un problème célèbre est celui qui répond au nom de "3-SAT" et qui ressemble un peu au problème du coloriage d'un graphe de n sommets avec 3 couleurs (cf. série 5): voir https://fr.wikipedia.org/wiki/Probl%C3%A8me_3-SAT pour plus de détails.
Une conjecture importante à propos de ce problème, baptisée "Exponential Time Hypothesis", est qu'on ne peut pas résoudre ce problème mieux qu'en un temps exponentiel en n (donc un temps de la forme exp(cn) avec c une constante plus grande que 0).
Pourquoi cette conjecture est-elle importante? Car si on arrivait à montrer qu'elle est vraie, une conséquence directe serait que P n'est pas égal à NP, donc on obtiendrait une réponse à cette fameuse question que je mentionnais en cours.
Or hier, OpenAI a publié un résultat (encore sujet à vérification) démontrant que cette conjecture est... fausse:
Ceci ne permet donc pas de conclure quelque chose sur la fameuse question P vs NP... (c'est seulement si on avait démontré qu'elle était vraie qu'on aurait pu conclure quelque chose). Ceci dit, c'est un pas important dans la réflexion sur le sujet!
Meilleures salutations,
Olivier
