Azərbaycanca AzərbaycancaБеларускі БеларускіDansk DanskDeutsch DeutschEspañola EspañolaFrançais FrançaisIndonesia IndonesiaItaliana Italiana日本語 日本語Қазақ ҚазақLietuvos LietuvosNederlands NederlandsPortuguês PortuguêsРусский Русскийසිංහල සිංහලแบบไทย แบบไทยTürkçe TürkçeУкраїнська Українська中國人 中國人United State United StateAfrikaans Afrikaans
Підтримка
www.wikidata.uk-ua.nina.az

Задача розв язування задача алгоритмічного розпізнавання тривіального вузла якщо задано певне подання вузла тобто діагра

Задача розв'язування

Задача розв'язування

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

image
Дві прості діаграми тривіального вузла
image
Заплутана діаграма тривіального вузла (вузол Морвена Сіслвайта)
image
Тривіальний вузол Отіаї

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

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

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

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

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

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

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

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

  • Число рухів Рейдемейстера, необхідних для зведення діаграми тривіального вузла до стандартного вигляду не більше ніж поліноміальне від числа перетинів . Тому повний пошук усіх рухів Рейдемейстера може виявити тривіальність вузла за експоненціальний час.
  • Подібно до цього будь-які дві тріангуляризації одного доповнення вузла можна з'єднати послідовністю рухів Пахнера довжиною не більше подвійного експоненціалу від числа перетинів. Таким чином, можна визначити, чи є вузол тривіальним, перевіркою послідовностей рухів Пахнера цієї довжини, починаючи від доповнення заданого вузла, а потім перевіркою, чи не можна будь-який із цих рухів перетворити на стандартну тріангуляцію повного тора. Час цього методу мав би бути тричі експоненціальним, проте експерименти показують, що ці межі дуже песимістичні і потрібно значно менше рухів Пахнера.
  • Залишкова скінченність групи вузла (яка випливає з геометризації [ru]) дає алгоритм — перевіряємо, чи не містить група нециклічної скінченної факторгрупи. Ця ідея використовується в доведенні Куперберга, що завдання розв'язування належить до класу co-NP.
  • [en] вузла визначає рід вузла, який дорівнює 0 тоді і тільки тоді, коли вузол тривіальний. Комбінаторну версію гомології Флоєра вузла можна обчислити.
  • [en] визначає тривіальність вузла за результатами [en] і [en]. Складність гомології Хованова щонайменше така ж, як у задачі обчислення полінома Джонса, але його можна обчислити за допомогою алгоритму і програми Бар-Натана. Бар-Натан не дає строгого аналізу свого алгоритму, але евристичний передбачає, що алгоритм експоненціальний від шляхової ширини графа діаграми перетинів, яка, в свою чергу, не більша від квадратного кореня з числа перетинів (з деяким коефіцієнтом).

Складність цих алгоритмів активно вивчається.

Див. також

Примітки

  1. Hass, Lagarias, Pippenger, 1999.
  2. Hara, Tani, Yamamoto, 2005.
  3. Згадано як «часткове повідомлення» [15] у списку посилань статті Куперберга (Kuperberg, 2014).
  4. Kuperberg, 2014.
  5. Kawarabayashi, Kreutzer, Mohar, 2010.
  6. Ladd, Kavraki, 2004.
  7. Burton, 2011a.
  8. Birman, Hirsch, 1998.
  9. Lackenby, 2015.
  10. Mijatović, 2005.
  11. Burton, 2011b.
  12. Manolescu, Ozsváth, Sarkar, 2009.
  13. Kronheimer, Mrowka, 2011.
  14. Bar-Natan, 2007.

Література

  • Dror Bar-Natan. Fast Khovanov homology computations // . — 2007. — Т. 16, вип. 3 (17 червня). — С. 243—255. — arXiv:math.GT/0606318. — DOI:10.1142/S0218216507005294.
  • Joan S. Birman, Michael Hirsch. A new algorithm for recognizing the unknot // . — 1998. — Т. 2 (17 червня). — С. 178—220. — DOI:10.2140/gt.1998.2.175.
  • Benjamin A. Burton. Maximal admissible faces and asymptotic bounds for the normal surface solution space // . — 2024. — Т. 118, вип. 4 (17 червня). — С. 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 // . — 1961. — Т. 105 (17 червня). — С. 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 // . — 1999. — Т. 46, вип. 2 (17 червня). — С. 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 // . — 2001. — Т. 14, вип. 2 (17 червня). — С. 399—428. — DOI:10.1090/S0894-0347-01-00358-7.
  • Ken-ichi Kawarabayashi, Stephan Kreutzer, Bojan Mohar. . — 2010. — С. 97—106. — DOI:10.1145/1810959.1810975.
  • Peter Kronheimer, Tomasz Mrowka. Khovanov homology is an unknot-detector // . — 2011. — Т. 113, вип. 1 (17 червня). — С. 97—208. — arXiv:1005.4346. — DOI:10.1007/s10240-010-0030-y.
  • Greg Kuperberg. Knottedness is in NP, modulo GRH // . — 2014. — Т. 256 (17 червня). — С. 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 (17 червня). — С. 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 (17 червня). — С. 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 (17 червня). — С. 843—856. — arXiv:math/0306117. — DOI:10.4310/mrl.2005.v12.n6.a6.

Посилання

  • Інформація про класи складності та їх зв'язки — Complexity Zoo[ 27 серпня 2019 у Wayback Machine.]

Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет

Zadacha rozv yazuvannya zadacha algoritmichnogo rozpiznavannya trivialnogo vuzla yaksho zadano pevne podannya vuzla tobto diagrama vuzla Isnuye kilka vidiv algoritmiv rozv yazuvannya Osnovna nevirishena problema chi mozhna rozv yazati zadachu za polinomialnij chas tobto chi nalezhit zadacha do klasu skladnosti P Dvi prosti diagrami trivialnogo vuzlaZaplutana diagrama trivialnogo vuzla vuzol Morvena Sislvajta Trivialnij vuzol OtiayiObchislyuvalna skladnistPershi kroki u viznachenni obchislyuvalnoyi skladnosti zrobleno v napryamku dovedennya sho zadacha nalezhit do skladnishih klasiv skladnosti yaki mistyat klas P Z vikoristannyam en dlya opisu poverhon Zejferta zadanogo vuzla Gass Lagarias i Pippendzher pokazali sho zadacha rozv yazuvannya nalezhit do klasu skladnosti NP Hara Tani i Yamamoto zayavili sho rozv yazuvannya nalezhit klasu en Piznishe odnak voni vidklikali svoyu zayavu 2011 roku en doviv sho za umovi istinnosti uzagalnenoyi gipotezi Rimana zadacha rozv yazuvannya nalezhit do klasu co NP Zadacha rozv yazuvannya maye taku samu obchislyuvalnu skladnist yak i perevirka chi ye vkladennya neoriyentovanogo grafa v evklidiv prostir nezacheplenim Vuzol Otiayi sho mistit 139 vershin napriklad spershu buv rozv yazanij za dopomogoyu komp yutera za 108 godin ale zgodom chas skorocheno do 10 hvilin Algoritmi rozv yazuvannyaDeyaki algoritmi rozv yazuvannya zadachi rozv yazuvannya gruntuyutsya na teoriyi en en Algoritm Gakena vikoristovuye teoriyu normalnih poverhon dlya poshuku diska mezha yakogo zavuzlena Gaken spochatku vikoristovuvav cej algoritm shob pokazati sho zadachu rozv yazuvannya mozhna rozv yazati ale vin ne analizuvav obchislyuvalnoyi skladnosti algoritmu detalno Gass Lagarias i Pippendzher pokazali sho mnozhinu vsih normalnih poverhon mozhna podati yak cili tochki v bagatogrannomu konusi i sho poverhnyu yaka svidchit pro mozhlivist rozv yazannya krivoyi yaksho taka isnuye mozhna zavzhdi znajti na odnomu z krajnih promeniv cogo konusa Takim chinom metodi pererahuvannya vershin mozhna vikoristati dlya pererahuvannya vsih krajnih promeniv i perevirki chi ne ye voni zavuzlenimi mezhami diska Gass Lagarias i Pippendzher vikoristali cej metod shob pokazati sho vidshukannya rozv yazku nalezhit do klasu NP Piznishe doslidniki zokrema Barton polipshili yihnij analiz pokazavshi sho cej algoritm korisnij mayuchi nevisokogo poryadku eksponentnu skladnist yak funkciyu vid chisla peretiniv Algoritm Birmana i Girsha vikoristovuye desho inshu strukturu vidminnu vid normalnoyi poverhni Odnak dlya analizu yihnoyi povedinki voni povernulisya do teoriyi normalnih poverhon Inshi pidhodi Chislo ruhiv Rejdemejstera neobhidnih dlya zvedennya diagrami trivialnogo vuzla do standartnogo viglyadu ne bilshe nizh polinomialne vid chisla peretiniv Tomu povnij poshuk usih ruhiv Rejdemejstera mozhe viyaviti trivialnist vuzla za eksponencialnij chas Podibno do cogo bud yaki dvi triangulyarizaciyi odnogo dopovnennya vuzla mozhna z yednati poslidovnistyu ruhiv Pahnera dovzhinoyu ne bilshe podvijnogo eksponencialu vid chisla peretiniv Takim chinom mozhna viznachiti chi ye vuzol trivialnim perevirkoyu poslidovnostej ruhiv Pahnera ciyeyi dovzhini pochinayuchi vid dopovnennya zadanogo vuzla a potim perevirkoyu chi ne mozhna bud yakij iz cih ruhiv peretvoriti na standartnu triangulyaciyu povnogo tora Chas cogo metodu mav bi buti trichi eksponencialnim prote eksperimenti pokazuyut sho ci mezhi duzhe pesimistichni i potribno znachno menshe ruhiv Pahnera Zalishkova skinchennist grupi vuzla yaka viplivaye z geometrizaciyi ru daye algoritm pereviryayemo chi ne mistit grupa neciklichnoyi skinchennoyi faktorgrupi Cya ideya vikoristovuyetsya v dovedenni Kuperberga sho zavdannya rozv yazuvannya nalezhit do klasu co NP en vuzla viznachaye rid vuzla yakij dorivnyuye 0 todi i tilki todi koli vuzol trivialnij Kombinatornu versiyu gomologiyi Floyera vuzla mozhna obchisliti en viznachaye trivialnist vuzla za rezultatami en i en Skladnist gomologiyi Hovanova shonajmenshe taka zh yak u zadachi obchislennya polinoma Dzhonsa ale jogo mozhna obchisliti za dopomogoyu algoritmu i programi Bar Natana Bar Natan ne daye strogogo analizu svogo algoritmu ale evristichnij peredbachaye sho algoritm eksponencialnij vid shlyahovoyi shirini grafa diagrami peretiniv yaka v svoyu chergu ne bilsha vid kvadratnogo korenya z chisla peretiniv z deyakim koeficiyentom Skladnist cih algoritmiv aktivno vivchayetsya Div takozh en Chislo rozv yazuvannyaPrimitkiHass Lagarias Pippenger 1999 Hara Tani Yamamoto 2005 Zgadano yak chastkove povidomlennya 15 u spisku posilan statti Kuperberga Kuperberg 2014 Kuperberg 2014 Kawarabayashi Kreutzer Mohar 2010 Ladd Kavraki 2004 Burton 2011a Birman Hirsch 1998 Lackenby 2015 Mijatovic 2005 Burton 2011b Manolescu Ozsvath Sarkar 2009 Kronheimer Mrowka 2011 Bar Natan 2007 LiteraturaDror Bar Natan Fast Khovanov homology computations 2007 T 16 vip 3 17 chervnya S 243 255 arXiv math GT 0606318 DOI 10 1142 S0218216507005294 Joan S Birman Michael Hirsch A new algorithm for recognizing the unknot Geometry amp Topology 1998 T 2 17 chervnya S 178 220 DOI 10 2140 gt 1998 2 175 Benjamin A Burton Maximal admissible faces and asymptotic bounds for the normal surface solution space 2024 T 118 vip 4 17 chervnya S 1410 1435 arXiv 1004 2605 DOI 10 1016 j jcta 2010 12 011 z dzherela 3 kvitnya 2016 Procitovano 16 travnya 2021 Benjamin Burton 1 2011b S 153 162 DOI 10 1145 1998196 1998220 z dzherela 25 bereznya 2016 Wolfgang Haken Theorie der Normalflachen 1961 T 105 17 chervnya S 245 375 DOI 10 1007 BF02559591 Masao Hara Seiichi Tani Makoto Yamamoto Proc 16th ACM SIAM Symposium on Discrete algorithms SODA 05 2005 S 359 364 Joel Hass Jeffrey C Lagarias Nicholas Pippenger The computational complexity of knot and link problems 1999 T 46 vip 2 17 chervnya S 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 2001 T 14 vip 2 17 chervnya S 399 428 DOI 10 1090 S0894 0347 01 00358 7 Ken ichi Kawarabayashi Stephan Kreutzer Bojan Mohar 2010 S 97 106 DOI 10 1145 1810959 1810975 Peter Kronheimer Tomasz Mrowka Khovanov homology is an unknot detector 2011 T 113 vip 1 17 chervnya S 97 208 arXiv 1005 4346 DOI 10 1007 s10240 010 0030 y Greg Kuperberg Knottedness is in NP modulo GRH 2014 T 256 17 chervnya S 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 T 182 vip 2 17 chervnya S 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 T 7 S 7 23 Springer Tracts in Advanced Robotics DOI 10 1007 978 3 540 45058 0 2 Ciprian Manolescu Peter S Ozsvath Sucharit Sarkar A combinatorial description of knot Floer homology Annals of Mathematics 2009 T 169 vip 2 17 chervnya S 633 660 arXiv math 0607691 DOI 10 4007 annals 2009 169 633 Aleksandar Mijatovic Simplical structures of knot complements Mathematical Research Letters 2005 T 12 vip 6 17 chervnya S 843 856 arXiv math 0306117 DOI 10 4310 mrl 2005 v12 n6 a6 PosilannyaInformaciya pro klasi skladnosti ta yih zv yazki Complexity Zoo 27 serpnya 2019 u Wayback Machine

Дата публікації:
Топ