Como posso calcular nós?

11

Existe uma maneira documentada de calcular nós? (circunferências embutidas em um espaço euclidiano tridimensional).

Quero dizer, um tipo de dados para representá-los e um algoritmo para determinar se duas instâncias do tipo de dados representam o mesmo nó.

Se a resposta for positiva, e a complexidade desse problema?

jota.191
fonte
7
Mesmo verificar se um determinado diagrama representa a desatar é um problema difícil: en.wikipedia.org/wiki/Unknotting_problem
Suresh Venkat
4
É possível representar nós como programas: veja este artigo de Meredith e Snyder. Nessa representação, os nós são isotópicos do ambiente sempre que suas codificações são fracamente bisimilares.
Martin Berger

Respostas:

12

As maneiras mais naturais de representar nós são incorporá-los linearmente por partes em (armazene as coordenadas dos vértices e onde você deseja colocar segmentos) (qualquer nó doméstico pode ser incorporado por partes linearmente) ou com um diagrama de nó, ou seja, armazenando uma projeção em como um gráfico, onde a cada cruzamento você especifica qual fio está acima.R 2R3R2

Como Suresh apontou, verificar a equivalência do nó é altamente não trivial (não se sabe que esteja em P), mas os resultados experimentais para o reconhecimento do nó são semelhantes a polinômios - a equivalência do nó parece muito mais difícil. Se você estiver procurando por software, dê uma olhada em Regina .

Arnaud
fonte
10

Uma maneira tradicional de representar nós é através de diagramas de nós. Para uma discussão sobre diagramas de nós, consulte "Nós, elos, tranças e 3 manifolds" de Prasolov e Sossinsky

O programa SnapPea representa nós na três esferas, convertendo um determinado diagrama de nós em uma triangulação do complemento do nó. As técnicas de simplificação da triangulação no SnapPea parecem reconhecer o nó em um segundo, para todos os diagramas de nó "do tamanho humano". Para o software SnapPy (atualização do SnapPea em Python) e muito mais, consulte o site CompuTop, mantido por Nathan Dunfield.

Ivan Dynnikov, em seu artigo "Abordagem de três páginas à teoria dos nós", forneceu uma estrutura de dados nova e muito interessante para representar os nós. Isso também reconhece os nódulos muito rapidamente e levou a desenvolvimentos interessantes na homologia do Heegaard Floer - veja as discussões sobre links de grade.

Sam Nead
fonte