Jak mogę obliczyć węzły?

Czy istnieje udokumentowany sposób obliczania węzłów? (obwody osadzone w trójwymiarowej przestrzeni euklidesowej).

Mam na myśli typ danych, który je reprezentuje, oraz algorytm określający, czy dwa wystąpienia typu danych reprezentują ten sam węzeł.

Jeśli odpowiedź jest pozytywna, co ze złożonością tego problemu?

Najbardziej naturalnym sposobem przedstawiania węzłów jest albo osadzenie ich fragmentarycznie liniowo w (wystarczy zapisać współrzędne wierzchołków i miejsce, w którym chcesz umieścić segmenty) (dowolny oswojony węzeł można osadzić fragmentarycznie liniowo) lub za pomocą schemat węzła, tj. przechowujący rzut na jako wykres, gdzie przy każdym skrzyżowaniu określasz, która nić jest powyżej.$\mathbb{R}^3$$\mathbb{R}^2$

Jak zauważył Suresh, sprawdzanie równoważności węzłów jest wysoce nietrywialne (nie wiadomo, że występuje w P), ale wyniki eksperymentalne rozpoznawania węzłów są wielomianowe - równoważność węzłów wygląda jednak znacznie trudniej. Jeśli szukasz oprogramowania, zajrzyj do Reginy .

Tradycyjnym sposobem przedstawiania węzłów są diagramy węzłów. Omówienie diagramów węzłów znajduje się w „Węzłach, ogniwach, warkoczach i 3-rozmaitościach” Prasołowa i Sossinsky'ego

Program SnapPea reprezentuje węzły w trójkuli, przekształcając dany diagram węzłów w triangulację dopełnienia węzła. Techniki uproszczenia triangulacji w SnapPea wydają się rozpoznawać brak węzła w ciągu sekundy, dla wszystkich diagramów węzłów „wielkości człowieka”. Oprogramowanie SnapPy (aktualizacja SnapPea w Pythonie) i wiele innych znajduje się na stronie CompuTop, którą prowadzi Nathan Dunfield.

Ivan Dynnikov w swoim artykule „Trzystronicowe podejście do teorii węzłów” przedstawił nową i bardzo interesującą strukturę danych do reprezentowania węzłów. To także bardzo szybko rozpoznaje węzły i doprowadziło do interesujących zmian w homologii Heegaard Floer - patrz dyskusje na temat linków siatki.