2026-03-20 12:47 UTC
Et tous ces problèmes "équivalents" et qu'on sait pas résoudre mieux, on les appelle des problèmes "NP complet" (c'est très résumé hein, mais c'est l'idée générale)
Replies (1)
-
@pyviv@social.sciences.re 2026-03-20 12:52
Et Joseph Dorfer a démontré que le calcul de la distance de flip est NP-complet donc en gros, il est équivalent à tous les autres problèmes relous qu'on a déjà. Ça veut dire que c'est PAS LA PEINE d'essayer de se prendre la tête à trouver un algorithme efficace parce qu'on VA PAS Y ARRIVER Mais c'est pas grave hein ! Ça veut dire qu'on peut mettre son énergie ailleurs, par exemple calculer des solutions approchées