Elektrine lite

← Feed

@pyviv@social.sciences.re

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

    Open ##2339769