Задача развязывания — задача алгоритмического распознавания тривиального узла если задано некоторое представление узла, то есть диаграмма узла. Существует несколько видов алгоритмов развязывания. Основная нерешённая проблема — можно ли решить задачу за полиномиальное время, то есть, принадлежит ли задача классу сложности P.
Вычислительная сложность
Первые шаги в определении вычислительной сложности были предприняты в сторону доказательства, что задача принадлежит более сложным классам сложности, содержащим класс P. С использованием нормальных поверхностей для описания поверхностей Зейферта заданного узла Хасс, Лагариас и Пиппенжер[1] показали, что задача развязывания принадлежит классу сложности NP. Хара, Тани и Ямамото[2] заявили, что развязывание принадлежит классу AM ∩ co-AM. Позднее, однако, они отозвали своё заявление[3]. В 2011 Грег Куперберг доказал, что (в предположении верности обобщённой гипотезы Римана) задача развязывания принадлежит классу co-NP[4].
Задача развязывания имеет ту же вычислительную сложность, что и проверка, является ли вложение неориентированного графа в евклидово пространство незацепленным[5].
Узел Отиаи, содержащий 139 вершин, например, был сперва развязан с помощью компьютера за 108 часов, но это время впоследствии сокращено до 10 минут[6]
Алгоритмы развязывания
Некоторые алгоритмы решения задачи развязывания основываются на теории Хакена нормальных поверхностей:
- Алгоритм Хакена использует теорию нормальных поверхностей для поиска диска, граница которого заузлена. Хакен изначально использовал этот алгоритм, чтобы показать, что задача развязывания разрешима, но он не анализировал вычислительную сложность алгоритма детально.
- Хасс, Лагариас и Пиппенджер показали, что множество всех нормальных поверхностей можно представить как целые точки в многогранном конусе и что поверхность, свидетельствующая о возможности развязывания кривой (если таковая существует), может быть всегда найдена на одном из крайних лучей этого конуса. Таким образом, методы перечисления вершин могут быть использованы для перечисления всех крайних лучей и проверки, не являются ли они заузлёнными границами диска. Хасс, Лагариас и Пиппенджер использовали этот метод, чтобы показать, что нахождение развязывания принадлежит классу NP. Позднее исследователи, такие как Бартон[7] улучшили их анализ, показав, что этот алгоритм может быть полезен, имея невысокого порядка экспоненциальную сложность (как функцию от числа пересечений).
- Алгоритм Бирмана и Хирша[8] использует расслоение кос, несколько другую структуру, отличную от нормальной поверхности. Однако для анализа их поведения они вернулись к теории нормальных поверхностей.
Другие подходы:
- Число движений Рейдемейстера, необходимых для приведения диаграммы тривиального узла к стандартному виду не более чем полиномиально от числа пересечений[9]. Поэтому, полный поиск всех движений Рейдемейстера может обнаружить тривиальность узла за экспоненциальное время.
- Похожим образом любые две триангуляризации одного и того же дополнения узла могут быть соединены последовательностью движений Пачнера длиной не больше двойного экспоненциала от числа пересечений[10]. Таким образом, можно определить, является ли узел тривиальным путём проверки последовательностей движений Пачнера этой длины, начиная с дополнения заданного узла, а затем проверки, нельзя ли какое-либо из этих движений преобразовать в стандартную триануляцию полного тора. Время этого метода должно бы быть трижды экспоненциальным, однако эксперименты показывают, что эти границы очень пессимистичны и нужно куда меньше движений Пачнера[11].
- Остаточная конечность группы узла (которая следует из геометризации многообразий Хакена) даёт алгоритм — проверяем, не содержит ли группа нециклическую конечную факторгруппу. Эта идея используется в доказательстве Куперберга, что задача развязывания входит в класс co-NP.
- Гомология Флоера узла определяет род узла, который равен 0 тогда и только тогда, когда узел тривиален. Комбинаторная версия гомологии Флоера узла может быть вычислена[12].
- Гомология Хованова определяет тривиальность узла согласно результатам Кронхеймера и Мровки[13]. Сложность гомологии Хованова по меньшей мере такая же как у #P-трудной задачи вычисления полинома Джонса, но он может быть вычислен с помощью алгоритма и программы Бар-Натана[14]. Бар-Натан не даёт строгого анализа своего алгоритма, но эвристически предполагает, что алгоритм экспоненциален от путевой ширины графа диаграммы пересечений, которая, в свою очередь, не больше квадратного корня от числа пересечений (с некоторым коэффициентом).
Изучение сложности этих алгоритмов активно продолжается.
См. также
Примечания
- ↑ Hass, Lagarias, Pippenger, 1999.
- ↑ Hara, Tani, Yamamoto, 2005.
- ↑ Упомянуто как «частное сообщение» [15] в списке ссылок статьи Куперберга (Kuperberg, 2014).
- ↑ Kuperberg, 2014.
- ↑ Kawarabayashi, Kreutzer, Mohar, 2010.
- ↑ Ladd, Kavraki, 2004.
- ↑ Burton, 2011a.
- ↑ Birman, Hirsch, 1998.
- ↑ Lackenby, 2015.
- ↑ Mijatović, 2005.
- ↑ Burton, 2011b.
- ↑ Manolescu, Ozsváth, Sarkar, 2009.
- ↑ Kronheimer, Mrowka, 2011.
- ↑ Bar-Natan, 2007.
Литература
- Dror Bar-Natan. Fast Khovanov homology computations // Journal of Knot Theory and Its Ramifications. — 2007. — Т. 16, вып. 3. — С. 243—255. — doi:10.1142/S0218216507005294. — arXiv:math.GT/0606318.
- Joan S. Birman, Michael Hirsch. A new algorithm for recognizing the unknot // Geometry and Topology. — 1998. — Т. 2. — С. 178—220. — doi:10.2140/gt.1998.2.175.
- Benjamin A. Burton. Maximal admissible faces and asymptotic bounds for the normal surface solution space // Journal of Combinatorial Theory. — 2011a. — Т. 118, вып. 4. — С. 1410—1435. — doi:10.1016/j.jcta.2010.12.011. — arXiv:1004.2605.
- Benjamin Burton. Proc. 27th ACM Symposium on Computational Geometry. — 2011b. — С. 153—162. — doi:10.1145/1998196.1998220.
- Wolfgang Haken. Theorie der Normalflächen // Acta Mathematica. — 1961. — Т. 105. — С. 245—375. — doi:10.1007/BF02559591.
- Masao Hara, Seiichi Tani, Makoto Yamamoto. Proc. 16th ACM-SIAM Symposium on Discrete algorithms (SODA '05). — 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:10.1145/301970.301971. — arXiv:math/9807016.
- Joel Hass, Jeffrey C. Lagarias, Nicholas Pippenger. The number of Reidemeister moves needed for unknotting // Journal of the American Mathematical Society. — 2001. — Т. 14, вып. 2. — С. 399—428. — doi:10.1090/S0894-0347-01-00358-7.
- Ken-ichi Kawarabayashi, Stephan Kreutzer, Bojan Mohar. Proc. ACM Symposium on Computational Geometry (SoCG '10). — 2010. — С. 97—106. — doi:10.1145/1810959.1810975.
- Peter Kronheimer, Tomasz Mrowka. Khovanov homology is an unknot-detector // Publications Mathématiques de l'IHÉS. — 2011. — Т. 113, вып. 1. — С. 97—208. — doi:10.1007/s10240-010-0030-y. — arXiv:1005.4346.
- Greg Kuperberg. Knottedness is in NP, modulo GRH // Advances in Mathematics. — 2014. — Т. 256. — С. 493—506. — doi:10.1016/j.aim.2014.01.007. — arXiv:1112.0845.
- Marc Lackenby. A polynomial upper bound on Reidemeister moves // Annals of Mathematics. — 2015. — Т. 182, вып. 2. — С. 491—564. — doi:10.4007/annals.2015.182.2.3. — arXiv:1302.0180.
- 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:10.1007/978-3-540-45058-0_2.
- Ciprian Manolescu, Peter S. Ozsváth, Sucharit Sarkar. A combinatorial description of knot Floer homology // Annals of Mathematics. — 2009. — Т. 169, вып. 2. — С. 633—660. — doi:10.4007/annals.2009.169.633. — arXiv:math/0607691.
- Aleksandar Mijatović. Simplical structures of knot complements // Mathematical Research Letters. — 2005. — Т. 12, вып. 6. — С. 843—856. — doi:10.4310/mrl.2005.v12.n6.a6. — arXiv:math/0306117.
Ссылки
- Complexity Zoo Архивная копия от 27 августа 2019 на Wayback Machine даёт информацию о классах сложности и их связях.
Эта страница в последний раз была отредактирована 3 марта 2023 в 07:52.
Как только страница обновилась в Википедии она обновляется в Вики 2.
Обычно почти сразу, изредка в течении часа.
Обычно почти сразу, изредка в течении часа.