Mastodawn

Dr Pyviv Mar 20

Alors comme promis, je vais vous raconter le problème que semble avoir résolu Joseph Dorfer dans cet article récent

https://arxiv.org/abs/2602.22874

À noter que j'écris "semble" car l'article est très récent et donc pas encore publié dans une revue où il aurait été relu par d'autres chercheurs ou chercheuses et que sur un résultat de cette ampleur, on reste toujours prudent. Mais je n'ai aucun doute sur le sérieux de l'article

Flip Distance of Triangulations of Convex Polygons / Rotation Distance of Binary Trees is NP-complete

Flips in triangulations of convex polygons arise in many different settings. They are isomorphic to rotations in binary trees, define edges in the 1-skeleton of the Associahedron and cover relations in the Tamari Lattice. The complexity of determining the minimum number of flips that transform one triangulation of a convex point set into another remained a tantalizing open question for many decades. We settle this question by proving that computing shortest flip sequences between triangulations of convex polygons, and therefore also computing the rotation distance of binary trees, is NP-hard. For our proof we develop techniques for flip sequences of triangulations whose counterparts were introduced for the study of flip sequences of non-crossing spanning trees by Bjerkevik, Kleist, Ueckerdt, and Vogtenhuber~[SODA25] and Bjerkevik, Dorfer, Kleist, Ueckerdt, and Vogtenhuber~[SoCG26].

arXiv.org

Dr Pyviv Mar 20

Donc on va commencer avec un "polygone convexe", on prendra comme exemple un octogone comme sur ce dessin

Dr Pyviv Mar 20

Convexe signifie qu'aucun des points n'est "au milieu" des autres : je ne peux pas entourer un point avec des segments entre les autres points

Par exemple, cet autre polygone n'est pas convexe

Dr Pyviv Mar 20

On va "trianguler" notre polygone convexe : c'est à dire qu'on va former des triangles en reliant les points entre eux. C'est ce qu'on va appeler une "triangulation"

Dr Pyviv Mar 20

Pourquoi on fait ça ? Heu.. Parce qu'on a envie ?
En vrai, le triangle est la forme "la plus simple" et donc qu'on fasse de l'informatique graphique ou de la géométrie des polytopes, on va souvent découper les trucs en triangle car en math et info, on aime bien simplifier les choses

Dr Pyviv Mar 20

Et comme on aime découper en triangle, il y a des gens qui étudient toutes les façons de découper en triangle (genre moi je fais ça parfois).

Car oui, il y a plusieurs façons de faire ce découpage. Pour l'octogone de tout à l'heure, je vous ai montré un exemple mais il y a 132 façons différentes. On sait compter ça en combinatoire, ça s'appelle les nombres de Catalan, c'est mes nombres préférés

https://fr.wikipedia.org/wiki/Nombre_de_Catalan

Nombre de Catalan — Wikipédia

Dr Pyviv Mar 20

Et ce qui va nous intéresser aujourd'hui, c'est qu'on peut passer d'une triangulation à l'autre en modifiant juste une diagonale. Ça s'appelle un "flip" on choisit une diagonale, on la supprime et on la remplace par la seule autre diagonale possible qui forme une triangulation

Voilà un exemple

Dr Pyviv Mar 20

Et ce qu'on peut démontrer assez facilement, c'est que sur un polygone : on peut passer de n'importe quelle triangulation à n'importe quelle autre juste en faisant une série de "flip".

Voyez par exemple sur cette page le "graphe de flip" des 14 triangulations d'un hexagone

https://www.researchgate.net/figure/The-flip-graph-of-a-convex-hexagon-the-graph-of-the-3-dimensional-associahedron_fig4_365369610

Dr Pyviv Mar 20

Maintenant qu'on sait ça, on se pose une question toute simple : voilà 2 triangulations de mon polygone, c'est quoi la façon la plus rapide de passer de l'une à l'autre en faisant des flips? (c'est à dire le moins de flip possible)

Dr Pyviv Mar 20

Et là, C'EST LE DRAME !! On ne sait pas !! Évidemment, on peut calculer le graphe complet de toutes les triangulations, mais heu il y en a beaucoup, plus précisément le nombre de triangulations augmente de façon exponentielle par rapport au nombre de sommets.

Pour un polygone de 50 sommets, j'ai déjà plusieurs milliards de milliards de milliards de triangulations possibles. Donc no way de calculer le graphe complet 🤷🏼‍♀️

Dr Pyviv Mar 20

Donc la question qui était ouverte jusqu'à présent, c'est étant donné 2 triangulations d'un polygone, quelle est la complexité du calcul de la "distance de flip", c'est à dire le plus court chemin entre les deux.
"complexité" en gros ça veut dire le temps théorique en fonction du nombre de sommets dans mon polygone

Dr Pyviv Mar 20

On peut se demander pourquoi on veut savoir ça. Donc déjà je vous ai dit que les triangles et les triangulations, on aimait bien ça mais peut-être ça vous convainc pas assez. Mais il se trouve qu'en plus, les triangulations peuvent être transformées en plein d'autres choses !!

Par exemple, si je mets un point dans chaque triangle et que je relis ensemble les points qui sont dans des triangles qui se touchent, j'obtiens une autre structure qu'on appelle un arbre binaire

Dr Pyviv Mar 20

Et les arbres binaires, c'est un truc très très courant en informatique, en particulier en algorithmique parce que ça permet de représenter tout un tas de donnés en les séparant à chaque fois en 2 groupes.

Par exemple je vais mettre tous les mots qui commencent pat une lettre entre A et M à gauche, et tous les mots qui commencent par N... Z à droite. Puis je vais redécouper à gauche et à droite en 2 nouveaux groupes etc.

Dr Pyviv Mar 20

Donc l'arbre binaire modélise plein de trucs intéressant et se retrouve dans plein d'algo. Et en plus, le "flip" sur la triangulation correspond à ce qu'on appelle la "rotation" sur l'arbre binaire qui permet de faire pencher l'arbre sur la gauche ou sur la droite.

C'est une opération très courante et utile. Ce qui fait qu'on aimerait bien savoir comment on calcule la "distance de rotation" entre deux arbres, aka la "distance de flip" entre les triangulations et surtout savoir si on peut le faire de façon efficace

Dr Pyviv Mar 20

Et là le gros résultat de Joseph Dorfer c'est que : eh bah non ! Si on n'a pas réussi à trouver un algo sympa pour calculer cette distance c'est pas parce qu'on est nul, c'est parce que c'est très certainement pas possible !

Dr Pyviv Mar 20

Donc là, on va parler un "tout petit peu" de théorie de la complexité. Un truc qui prend la tête de toute la communauté informatique c'est le problème "P = NP"

https://fr.wikipedia.org/wiki/Probl%C3%A8me_P_%E2%89%9F_NP

Problème P ≟ NP — Wikipédia

Dr Pyviv Mar 20

En gros, en théorie de la complexité, on range les problèmes en fonction de à quel point on peut les résoudre de façon efficace ou non. Et en gros, on a des problèmes qu'on sait résoudre pas trop mal et d'autres pas du tout

Ceux qu'on sait pas résoudre, on a jamais réussi à démonter que c'était vraiment pas possible de le faire de façon efficace, mais on pense que c'est une impossibilité structurelle inhérente au problème lui même, c'est la conjoncture que "P est différent de NP"

Mais on a mis tous les problèmes irrésolubles ensemble et on a démontré qu'ils étaient équivalent entre eux (en gros, si on sait en résoudre un, on sait résoudre les autres _ si je sais calculer un certain bidule dans un graphe, je vais réussir à calculer une solution d'une certaine équation)

Dr Pyviv Mar 20

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)

Dr Pyviv Mar 20

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

Dr Pyviv Mar 20

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

Flip Distance Between Triangulations of a Simple Polygon is NP-Complete

Let T be a triangulation of a simple polygon. A flip in T is the operation of removing one diagonal of T and adding a different one such that the resulting graph is again a triangulation. The flip distance between two triangulations is the smallest number of flips required to transform one triangulation into the other. For the special case of convex polygons, the problem of determining the shortest flip distance between two triangulations is equivalent to determining the rotation distance between two binary trees, a central problem which is still open after over 25 years of intensive study. We show that computing the flip distance between two triangulations of a simple polygon is NP-complete. This complements a recent result that shows APX-hardness of determining the flip distance between two triangulations of a planar point set.

arXiv.org

Dr Pyviv Mar 20

L'un des auteurs est le directeur de thèse de Joseph Dorfer avec qui j'ai beaucoup discuté de ce problème. Une triangulation d'un polygone non convexe ça peut ressembler à ça

La preuve fabriquait des espèces de "tunnels" comme sur l'image donc, une chose est sûre, la nouvelle démonstration de Joseph Dorfer doit être très différente. En tout cas, c'est un magnifique résultat et je vais devoir mettre à jour tous mes projets de recherche !!

Dr Pyviv 6d ago

Je rajoute en conclusion : ce résultat signifie que si vous trouvez un algorithme efficace pour calculer la distance de flip entre 2 triangulations, alors vous cassez la sécurité informatique mondiale 🤷🏼‍♀️

(pourquoi ? Parce que les 2 sont des algorithmes "NP-complet" donc équivalent)

Est ce qu'il est prouvé que tout les problèmes NP-complet ont la même complexité ?

N'est il pas possible d'envisager qu'il y ait des classes de complexité différentes, dans le même genre qu'il y a des infinis plus grands que d'autres ?

Dr Pyviv 6d ago

@tanavit en fait, les problèmes sont démontrés comme étant équivalent : on peut utiliser la solution de l'un pour en résoudre un autre. En gros, on peut coder la division des grands nombres avec des flips de triangulations

@pyviv @tanavit Et puis la complexité est un zoo ! Ici on parle de complexité "au pire", donc on prend en compte ce qui se passe pour les polygones les plus difficiles ! Mais une méthode peut néanmoins bien marcher quasiment tout le temps (exemple de l'algorithme du simplexe) et mal se comporter uniquement sur des exemples pathologiques qui ne se rencontrent pas en pratique. Il y a d'autres notions de complexités (en moyenne, lissée ...) qui visent à capturer ça, qui peuvent donner une vision différente de la difficulté d'un pb.

Le Néandertal se sent las, las 6d ago

@thoasm @pyviv @tanavit donc pour certains ou même la plupart des problèmes NP complets il y a des méthodes qui marchent "bien" sur des exemples "typiques" (les mots entre guillemets sont à définir et on imagine qu'il y a plusieurs façons rigoureuses de le faire). De plus tous les problèmes NP complets se réduisent les uns aux autres.

Est-ce qu'après réduction, disons, du problème du voyageur du commerce à SAT, les exemples typiques de problème de voyageur commerce produisent des exemples typiques de SAT ? (Et vive versa œuf corse).

Et est-ce qu'il y a une réduction de SAT vers le voyageur du commerce qui permet de retrouver le problème de départ, ou on se retrouve avec deux problèmes de voyageurs du commerce équivalents de façon non triviale, le second sur un graphe beaucoup plus gros que le premier ?

Est-ce que ce genre de considération permet de hiérarchiser les problèmes NP complets ? Voire les méthodes de réduction ?

@HydrePrever @pyviv @tanavit
C'est de très bonne questions mais à ma connaissance (qui date un peu beaucoup) c'est des trucs qu'on sait pas trop faire.

Il y a pas mal de problèmes pour lesquels on peut classer des sous-classes en plus faciles si elles ont telles ou telle structures. Il y a des travaux statistiques sur la structures des problèmes particuliers pour déterminer ce qui le rend difficile, par exemple pour SAT et des instances aléatoires https://cgi.cse.unsw.edu.au/~tw/gwki94.pdf (sachant que les instances pratiques sont rarement "aléatoires"), mais relativiser tout ça avec des réduction … j'ai pas connaissance (mais c'est que moi).

@HydrePrever @pyviv @tanavit
Et le seul requis pour les réduction est que la transformation soit polynomiale. Elle n'est généralement pas du tout "bijective", c'est une injection qui ne fonctionne généralement pas dans l'autre sens. Donc pas vraiment de garantie de préservation des structures en général, en tout cas trivialement.