PROFILPELAJAR.COM

Задача розв'язування — задача алгоритмічного розпізнавання тривіального вузла якщо задано певне подання вузла, тобто діаграма вузла. Існує кілька видів алгоритмів розв'язування. Основна невирішена проблема — чи можна розв'язати задачу за поліноміальний час, тобто, чи належить задача до класу складності P.

Обчислювальна складність

Перші кроки у визначенні обчислювальної складності зроблено в напрямку доведення, що задача належить до складніших класів складності, які містять клас P. З використанням нормальних поверхонь^[en] для опису поверхонь Зейферта заданого вузла Гасс, Лагаріас і Піппенджер^[1] показали, що задача розв'язування належить до класу складності NP. Хара, Тані і Ямамото^[2] заявили, що розв'язування належить класу AM ∩ co-AM^[en]. Пізніше, однак, вони відкликали свою заяву^[3]. 2011 року Грег Куперберг^[en] довів, що (за умови істинності узагальненої гіпотези Рімана) задача розв'язування належить до класу co-NP^[4].

Задача розв'язування має таку саму обчислювальну складність, як і перевірка, чи є вкладення неорієнтованого графа в евклідів простір незачепленим^[5].

Вузол Отіаї, що містить 139 вершин, наприклад, спершу був розв'язаний за допомогою комп'ютера за 108 годин, але згодом час скорочено до 10 хвилин^[6].

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

Деякі алгоритми розв'язування задачі розв'язування ґрунтуються на теорії Гакена^[en] нормальних поверхонь^[en]:

Алгоритм Гакена використовує теорію нормальних поверхонь для пошуку диска, межа якого завузлена. Гакен спочатку використовував цей алгоритм, щоб показати, що задачу розв'язування можна розв'язати, але він не аналізував обчислювальної складності алгоритму детально.
Гасс, Лагаріас і Піппенджер показали, що множину всіх нормальних поверхонь можна подати як цілі точки в багатогранному конусі і що поверхню, яка свідчить про можливість розв'язання кривої (якщо така існує), можна завжди знайти на одному з крайніх променів цього конуса. Таким чином, методи перерахування вершин можна використати для перерахування всіх крайніх променів і перевірки, чи не є вони завузленими межами диска. Гасс, Лагаріас і Піппенджер використали цей метод, щоб показати, що відшукання розв'язку належить до класу NP. Пізніше дослідники, зокрема Бартон^[7], поліпшили їхній аналіз, показавши, що цей алгоритм корисний, маючи невисокого порядку експоненційну складність (як функцію від числа перетинів).
Алгоритм Бірмана і Гірша^[8] використовує розшарування кіс , дещо іншу структуру, відмінну від нормальної поверхні. Однак для аналізу їхньої поведінки вони повернулися до теорії нормальних поверхонь.

Інші підходи:

Число рухів Рейдемейстера, необхідних для зведення діаграми тривіального вузла до стандартного вигляду не більше ніж поліноміальне від числа перетинів^[9] . Тому повний пошук усіх рухів Рейдемейстера може виявити тривіальність вузла за експоненціальний час.
Подібно до цього будь-які дві тріангуляризації одного доповнення вузла можна з'єднати послідовністю рухів Пахнера довжиною не більше подвійного експоненціалу від числа перетинів^[10]. Таким чином, можна визначити, чи є вузол тривіальним, перевіркою послідовностей рухів Пахнера цієї довжини, починаючи від доповнення заданого вузла, а потім перевіркою, чи не можна будь-який із цих рухів перетворити на стандартну тріангуляцію повного тора. Час цього методу мав би бути тричі експоненціальним, проте експерименти показують, що ці межі дуже песимістичні і потрібно значно менше рухів Пахнера^[11].
Залишкова скінченність групи вузла (яка випливає з геометризації многовидів Гакена^[ru]) дає алгоритм — перевіряємо, чи не містить група нециклічної скінченної факторгрупи. Ця ідея використовується в доведенні Куперберга, що завдання розв'язування належить до класу co-NP.
Гомологія Флоєра^[en] вузла визначає рід вузла, який дорівнює 0 тоді і тільки тоді, коли вузол тривіальний. Комбінаторну версію гомології Флоєра вузла можна обчислити^[12].
Гомологія Хованова^[en] визначає тривіальність вузла за результатами Кронгеймера^[en] і Мровки^[en]^[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 (14 січня). — С. 243—255. — arXiv:math.GT/0606318. — DOI:10.1142/S0218216507005294.
Joan S. Birman, Michael Hirsch. A new algorithm for recognizing the unknot // Geometry & Topology. — 1998. — Т. 2 (14 січня). — С. 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. — 2025. — Т. 118, вип. 4 (14 січня). — С. 1410—1435. — arXiv:1004.2605. — DOI:10.1016/j.jcta.2010.12.011. Архівовано з джерела 3 квітня 2016. Процитовано 16 травня 2021.
Benjamin Burton. [1] — 2011b. — С. 153—162. — DOI:10.1145/1998196.1998220. Архівовано з джерела 25 березня 2016
Wolfgang Haken. Theorie der Normalflächen // Acta Mathematica. — 1961. — Т. 105 (14 січня). — С. 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 (14 січня). — С. 185—211. — arXiv:math/9807016. — DOI:10.1145/301970.301971.
Joel Hass, Jeffrey C. Lagarias, Nicholas Pippenger. The number of Reidemeister moves needed for unknotting // Journal of the American Mathematical Society. — 2001. — Т. 14, вип. 2 (14 січня). — С. 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 (14 січня). — С. 97—208. — arXiv:1005.4346. — DOI:10.1007/s10240-010-0030-y.
Greg Kuperberg. Knottedness is in NP, modulo GRH // Advances in Mathematics. — 2014. — Т. 256 (14 січня). — С. 493—506. — arXiv:1112.0845. — DOI:10.1016/j.aim.2014.01.007.
Marc Lackenby. A polynomial upper bound on Reidemeister moves // Annals of Mathematics. — 2015. — Т. 182, вип. 2 (14 січня). — С. 491—564. — (Second Series). — arXiv:1302.0180. — DOI:10.4007/annals.2015.182.2.3.
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 (14 січня). — С. 633—660. — arXiv:math/0607691. — DOI:10.4007/annals.2009.169.633.
Aleksandar Mijatović. Simplical structures of knot complements // Mathematical Research Letters. — 2005. — Т. 12, вип. 6 (14 січня). — С. 843—856. — arXiv:math/0306117. — DOI:10.4310/mrl.2005.v12.n6.a6.