Wie kann ich Knoten berechnen?

11

Gibt es eine dokumentierte Möglichkeit, Knoten zu berechnen? (Umfänge eingebettet in einen dreidimensionalen euklidischen Raum).

Ich meine, einen Datentyp, um sie darzustellen, und einen Algorithmus, um zu bestimmen, ob zwei Instanzen des Datentyps denselben Knoten darstellen.

Wenn die Antwort positiv ist, wie steht es dann mit der Komplexität dieses Problems?

ds.algorithms computability jota.191
quelle
7
Selbst zu überprüfen, ob ein bestimmtes Diagramm den Knoten darstellt, ist ein schwieriges Problem: en.wikipedia.org/wiki/Unknotting_problem
Suresh Venkat
4
Es ist möglich, Knoten als Programme darzustellen: siehe dieses Papier von Meredith und Snyder. In dieser Darstellung sind Knoten Umgebungsisotopen, wenn ihre Codierungen schwach bisimilar sind.
Martin Berger

Antworten:

12

R3R2

Wie Suresh betonte, ist die Überprüfung der Knotenäquivalenz höchst nicht trivial (nicht in P bekannt), aber die experimentellen Ergebnisse für die Erkennung von Knoten sind polynomartig - die Knotenäquivalenz sieht jedoch viel schwieriger aus. Wenn Sie nach Software suchen, schauen Sie sich Regina an .

Arnaud
quelle
10

Eine traditionelle Art, Knoten darzustellen, sind Knotendiagramme. Eine Diskussion der Knotendiagramme finden Sie unter "Knoten, Glieder, Geflechte und 3-Mannigfaltigkeiten" von Prasolov und Sossinsky

Das Programm SnapPea repräsentiert Knoten in der Dreikugel, indem ein gegebenes Knotendiagramm in eine Triangulation des Knotenkomplements umgewandelt wird. Die Triangulationsvereinfachungstechniken in SnapPea scheinen den Knoten innerhalb einer Sekunde für alle "menschlich großen" Knotendiagramme zu erkennen. Informationen zur Software SnapPy (Python-Upgrade von SnapPea) und vielem mehr finden Sie auf der Website CompuTop, die von Nathan Dunfield verwaltet wird.

Ivan Dynnikov hat in seiner Arbeit "Dreiseitiger Ansatz zur Knotentheorie" eine neue und sehr interessante Datenstruktur für die Darstellung von Knoten angegeben. Dies erkennt auch Unknoten sehr schnell und hat zu interessanten Entwicklungen in der Heegaard Floer-Homologie geführt - siehe die Diskussionen dort über Grid-Links.

Sam Nead
quelle