Elektrine lite

← Feed

@pyviv@social.sciences.re

2026-03-20 12:52 UTC

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

Replies (5)

  • @pyviv@social.sciences.re 2026-03-20 13:00

    Donc voilà, je vous ai résumé le résultat. Je ne sais pas du tout comment il le démontre car je n'ai pas encore lu l'article. Assez récemment, un autre article démontrait la NP-complétude de la distance de flip pour les polygones non convexe https://arxiv.org/abs/1209.0579

    Open ##2339770

  • @John_Livingston@mamot.fr 2026-03-20 13:00

    @pyviv@social.sciences.re Oh le plot flip!

    Open ##2339773

  • @pyviv@social.sciences.re Donc ça veut dire que la cryptographie est mathématiquement sécure ? Et pas seulement le one-time-pad, donc ? C'est gigantesque comme résultat ! (ou bien j'ai raté une étape ?)

    Open ##2339774

  • @pyviv@social.sciences.re Ou j'ai peut-être pas bien compris : il a démontré que P!=NP c'est bien ça ? (si oui c'est gigantesque) Ou bien juste qu'un problème particulier est NP-complet ? (sans que ça ne donne d'indication si oui ou non P=NP)

    Open ##2339776

  • @turbobob@mamot.fr 2026-03-20 14:47

    @pyviv@social.sciences.re Excellent 😄😊 !

    Open ##2339778