Comment calculer les nœuds?

11

Existe-t-il un moyen documenté de calculer les nœuds? (circonférences incrustées dans un espace euclidien tridimensionnel).

Je veux dire, un type de données pour les représenter, et un algorithme pour déterminer si deux instances du type de données représentent le même nœud.

Si la réponse est positive, qu'en est-il de la complexité de ce problème?

ds.algorithms computability jota.191
la source
7
Même vérifier si un diagramme donné représente le dénouement est un problème difficile: en.wikipedia.org/wiki/Unknotting_problem
Suresh Venkat
4
Il est possible de représenter les nœuds comme des programmes: voir cet article de Meredith et Snyder. Dans cette représentation, les nœuds sont isotopiques ambiants chaque fois que leurs encodages sont faiblement bisimilaires.
Martin Berger

Réponses:

12

R3R2

Comme l'a souligné Suresh, la vérification de l'équivalence des nœuds est très non triviale (on ne sait pas qu'elle se trouve dans P), mais les résultats expérimentaux pour la reconnaissance des nœuds sont de type polynomial - l'équivalence des nœuds semble cependant beaucoup plus difficile. Si vous cherchez un logiciel, jetez un œil à Regina .

Arnaud
la source
10

Une façon traditionnelle de représenter les nœuds est d'utiliser des diagrammes de nœuds. Pour une discussion sur les diagrammes de nœuds, voir "Noeuds, liens, tresses et 3 collecteurs" par Prasolov et Sossinsky

Le programme SnapPea représente des nœuds dans les trois sphères en convertissant un diagramme de nœuds donné en une triangulation du complément du nœud. Les techniques de simplification de la triangulation dans SnapPea semblent reconnaître le dénouement en une seconde, pour tous les diagrammes de nœuds «à taille humaine». Pour le logiciel SnapPy (mise à niveau Python de SnapPea) et bien d'autres, voir le site Web CompuTop, maintenu par Nathan Dunfield.

Ivan Dynnikov dans son article "Approche en trois pages de la théorie des nœuds" a donné une nouvelle structure de données très intéressante pour représenter les nœuds. Cela reconnaît également les nœuds très rapidement et a conduit à des développements intéressants dans l'homologie de Heegaard Floer - voir les discussions sur les mailles.

Sam Nead
la source