Задача развязывания — задача алгоритмического распознавания тривиального узла если задано некоторое представление узла, то есть диаграмма узла . Существует несколько видов алгоритмов развязывания. Основная нерешённая проблема — можно ли решить задачу за полиномиальное время , то есть, принадлежит ли задача классу сложности P .

Вычислительная сложность

Первые шаги в определении вычислительной сложности были предприняты в сторону доказательства, что задача принадлежит более сложным классам сложности, содержащим класс P. С использованием для описания поверхностей Зейферта заданного узла Хасс, Лагариас и Пиппенжер показали, что задача развязывания принадлежит классу сложности NP . Хара, Тани и Ямамото заявили, что развязывание принадлежит классу . Позднее, однако, они отозвали своё заявление . В 2011 доказал, что (в предположении верности обобщённой гипотезы Римана ) задача развязывания принадлежит классу co-NP .

Задача развязывания имеет ту же вычислительную сложность, что и проверка, является ли вложение неориентированного графа в евклидово пространство незацепленным .

Узел Отиаи, содержащий 139 вершин, например, был сперва развязан с помощью компьютера за 108 часов, но это время впоследствии сокращено до 10 минут

Алгоритмы развязывания

Некоторые алгоритмы решения задачи развязывания основываются на теории Хакена :

• Алгоритм Хакена использует теорию нормальных поверхностей для поиска диска, граница которого заузлена. Хакен изначально использовал этот алгоритм, чтобы показать, что задача развязывания разрешима, но он не анализировал вычислительную сложность алгоритма детально.
• Хасс, Лагариас и Пиппенджер показали, что множество всех нормальных поверхностей можно представить как целые точки в многогранном конусе и что поверхность, свидетельствующая о возможности развязывания кривой (если таковая существует), может быть всегда найдена на одном из крайних лучей этого конуса. Таким образом, могут быть использованы для перечисления всех крайних лучей и проверки, не являются ли они заузлёнными границами диска. Хасс, Лагариас и Пиппенджер использовали этот метод, чтобы показать, что нахождение развязывания принадлежит классу NP. Позднее исследователи, такие как Бартон улучшили их анализ, показав, что этот алгоритм может быть полезен, имея невысокого порядка экспоненциальную сложность (как функцию от числа пересечений).
• Алгоритм Бирмана и Хирша использует , несколько другую структуру, отличную от нормальной поверхности. Однако для анализа их поведения они вернулись к теории нормальных поверхностей.

Другие подходы:

• Число движений Рейдемейстера , необходимых для приведения диаграммы тривиального узла к стандартному виду не более чем полиномиально от числа пересечений . Поэтому, полный поиск всех движений Рейдемейстера может обнаружить тривиальность узла за экспоненциальное время.
• Похожим образом любые две триангуляризации одного и того же дополнения узла могут быть соединены последовательностью движений Пачнера длиной не больше двойного экспоненциала от числа пересечений . Таким образом, можно определить, является ли узел тривиальным путём проверки последовательностей движений Пачнера этой длины, начиная с дополнения заданного узла, а затем проверки, нельзя ли какое-либо из этих движений преобразовать в стандартную триануляцию полного тора . Время этого метода должно бы быть трижды экспоненциальным, однако эксперименты показывают, что эти границы очень пессимистичны и нужно куда меньше движений Пачнера .
• Остаточная конечность группы узла (которая следует из геометризации многообразий Хакена ) даёт алгоритм — проверяем, не содержит ли группа нециклическую конечную факторгруппу. Эта идея используется в доказательстве Куперберга, что задача развязывания входит в класс co-NP.
• узла определяет род узла, который равен 0 тогда и только тогда, когда узел тривиален. Комбинаторная версия гомологии Флоера узла может быть вычислена .
• определяет тривиальность узла согласно результатам и . Сложность гомологии Хованова по меньшей мере такая же как у #P-трудной задачи вычисления полинома Джонса , но он может быть вычислен с помощью алгоритма и программы Бар-Натана . Бар-Натан не даёт строгого анализа своего алгоритма, но эвристически предполагает, что алгоритм экспоненциален от путевой ширины графа диаграммы пересечений, которая, в свою очередь, не больше квадратного корня от числа пересечений (с некоторым коэффициентом).

Изучение сложности этих алгоритмов активно продолжается.

См. также

• Алгоритмическая топология
• Число развязывания (теория узлов)

Примечания

Литература

• Dror Bar-Natan. Fast Khovanov homology computations // . — 2007. — Т. 16 , вып. 3 . — С. 243—255 . — doi : . — arXiv : .
• Joan S. Birman, Michael Hirsch. A new algorithm for recognizing the unknot // . — 1998. — Т. 2 . — С. 178—220 . — doi : .
• Benjamin A. Burton. // Journal of Combinatorial Theory . — 2011a. — Т. 118 , вып. 4 . — С. 1410—1435 . — doi : . — arXiv : .
• Benjamin Burton. . — 2011b. — С. 153—162. — doi : .
• Wolfgang Haken. Theorie der Normalflächen // Acta Mathematica . — 1961. — Т. 105 . — С. 245—375 . — doi : .
• Masao Hara, Seiichi Tani, Makoto Yamamoto. . — 2005. — С. 359—364.
• Joel Hass, Jeffrey C. Lagarias, Nicholas Pippenger. The computational complexity of knot and link problems // Journal of the ACM . — 1999. — Т. 46 , вып. 2 . — С. 185—211 . — doi : . — arXiv : .
• Joel Hass, Jeffrey C. Lagarias, Nicholas Pippenger. The number of Reidemeister moves needed for unknotting // . — 2001. — Т. 14 , вып. 2 . — С. 399—428 . — doi : .
• Ken-ichi Kawarabayashi, Stephan Kreutzer, Bojan Mohar. . — 2010. — С. 97—106. — doi : .
• Peter Kronheimer, Tomasz Mrowka. Khovanov homology is an unknot-detector // Publications Mathématiques de l'IHÉS . — 2011. — Т. 113 , вып. 1 . — С. 97—208 . — doi : . — arXiv : .
• Greg Kuperberg. Knottedness is in NP, modulo GRH // Advances in Mathematics . — 2014. — Т. 256 . — С. 493—506 . — doi : . — arXiv : .
• Marc Lackenby. // Annals of Mathematics. — 2015. — Т. 182 , вып. 2 . — С. 491—564 . — doi : . — arXiv : .
• Andrew M. Ladd, Lydia E. Kavraki. Algorithmic Foundations of Robotics V / Jean-Daniel Boissonnat, Joel Burdick, Ken Goldberg, Seth Hutchinson. — Springer, 2004. — Т. 7. — С. 7—23. — (Springer Tracts in Advanced Robotics). — doi : .
• Ciprian Manolescu, Peter S. Ozsváth, Sucharit Sarkar. // Annals of Mathematics . — 2009. — Т. 169 , вып. 2 . — С. 633—660 . — doi : . — arXiv : .
• Aleksandar Mijatović. Simplical structures of knot complements // Mathematical Research Letters. — 2005. — Т. 12 , вып. 6 . — С. 843—856 . — doi : . — arXiv : .

Ссылки

• от 27 августа 2019 на Wayback Machine даёт информацию о классах сложности и их связях.