2026-03-20 12:52 UTC
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
-
@John_Livingston@mamot.fr 2026-03-20 13:00
@pyviv@social.sciences.re Oh le plot flip!
-
@lienrag@mastodon.tedomum.net 2026-03-20 13:06
@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 ?)
-
@lienrag@mastodon.tedomum.net 2026-03-20 13:08
@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)
-
@turbobob@mamot.fr 2026-03-20 14:47
@pyviv@social.sciences.re Excellent 😄😊 !