Как я могу вычислить узлы?

11

Есть ли документированный способ вычисления узлов? (окружности, вложенные в трехмерное евклидово пространство).

Я имею в виду тип данных для их представления и алгоритм для определения, представляют ли два экземпляра типа один и тот же узел.

Если ответ положительный, как насчет сложности этой проблемы?

ds.algorithms computability jota.191
источник
7
Даже проверить, представляет ли данная диаграмма узел, является сложной проблемой: en.wikipedia.org/wiki/Unknotting_problem
Suresh Venkat
4
Узлы можно представлять как программы: см. Эту статью Мередит и Снайдер. В этом представлении узлы являются изотопами окружающей среды всякий раз, когда их кодировки слабо бизоподобны.
Мартин Бергер

Ответы:

12

R3R2

Как указывал Суреш, проверка эквивалентности узлов весьма нетривиальна (неизвестно, что в P), но экспериментальные результаты распознавания узлов являются полиномиальными - эквивалентность узлов выглядит намного сложнее. Если вы ищете программное обеспечение, загляните в Regina .

Arnaud
источник
10

Один из традиционных способов представления узлов - это диаграммы узлов. Обсуждение диаграмм узлов см. В разделе «Узлы, зацепления, косы и 3-многообразия» Прасолова и Сосинского.

Программа SnapPea представляет узлы в трех сферах путем преобразования данной диаграммы узлов в триангуляцию дополнения узла. Методы упрощения триангуляции в SnapPea, по-видимому, распознают узел в течение секунды для всех диаграмм узлов "человеческого размера". Информацию о программном обеспечении SnapPy (обновление SnapPea на Python) и многом другом можно найти на веб-сайте CompuTop, поддерживаемом Натаном Данфилдом.

Иван Дынников в своей статье «Трехстраничный подход к теории узлов» дал новую и очень интересную структуру данных для представления узлов. Это также очень быстро распознает узлы и привело к интересным изменениям в гомологии Heegaard Floer - см. Обсуждения там по сеточным ссылкам.

Сэм Нид
источник