Úkol oddělení
Úkolem rozvázání je úkolem algoritmického rozpoznání triviálního uzlu , pokud je dáno nějaké znázornění uzlu, to jest diagram uzlu . Existuje několik typů odvazovacích algoritmů. Hlavním nevyřešeným problémem je, zda lze problém vyřešit v polynomiálním čase , tedy zda problém patří do třídy
složitosti P.
Výpočetní složitost
První kroky při definování výpočetní složitosti byly učiněny směrem k prokázání, že problém patří ke složitějším třídám složitosti obsahujícím třídu P. Pomocí normálních ploch k popisu Seifertových ploch daného uzlu ukázali Hass, Lagarias a Pippenger [1] že problém rozvázání patří do třídy složitosti NP . Hara, Tani a Yamamoto [2] uvedli, že rozvázání patří do třídy AM ∩ co-AM . Později však svou žádost stáhli [3] . V roce 2011 Greg Kuperberg dokázal, že (za předpokladu, že je zobecněná Riemannova hypotéza pravdivá ) problém nevázání patří do třídy co-NP [4] .
Problém untie má stejnou výpočetní složitost jako kontrola, zda vložení neorientovaného grafu v euklidovském prostoru není propojené [5] .
Uzel Ochiai, obsahující například 139 vrcholů, byl nejprve rozvázán pomocí počítače za 108 hodin, ale tato doba byla následně zkrácena na 10 minut [6]
Algoritmy zrušení vazby
Některé algoritmy pro řešení problému rozvázání jsou založeny na Hakenově teorii normálních povrchů :
- Hakenův algoritmus používá teorii normálních povrchů k nalezení disku, jehož hranice je zauzlená. Haken původně použil tento algoritmus, aby ukázal, že problém rozvázání je řešitelný, ale podrobně neanalyzoval výpočetní složitost algoritmu.
- Hass, Lagarias a Pippenger ukázali, že množinu všech normálních povrchů lze reprezentovat jako celočíselné body v mnohostěnném kuželu a že povrch indikující možnost rozvázání křivky (pokud existuje) lze vždy nalézt na jednom z extrémní paprsky tohoto kužele. Metody výčtu vertexů lze tedy použít k výčtu všech okrajových paprsků a ke kontrole, zda se jedná o zauzlované hranice disku . Hass, Lagarias a Pippenger použili tuto metodu, aby ukázali, že nalezení rozvázání patří do třídy NP. Pozdější výzkumníci jako Barton [7] zlepšili svou analýzu tím, že ukázali, že tento algoritmus může být užitečný s exponenciální složitostí nízkého řádu (jako funkce počtu průsečíků).
- Algoritmus Birmana a Hirsche [8] používá svazek copánku , mírně odlišnou strukturu než normální povrch. Aby však analyzovali jejich chování, vrátili se k teorii normálních povrchů.
Jiné přístupy:
- Počet Reidemeisterových pohybů potřebných k uvedení triviálního diagramu uzlu do standardního tvaru je nanejvýš polynomiální v počtu průsečíků [9] . Úplné prohledání všech Reidemeisterových tahů tedy může odhalit triviálnost uzlu v exponenciálním čase.
- Podobně mohou být libovolné dvě triangularizace téhož uzlového doplňku spojeny posloupností Pachnerových tahů o délce nejvýše dvojnásobku exponenciály počtu průniků [10] . Je tedy možné určit, zda je uzel triviální, kontrolou sekvencí Puchnerových pohybů této délky, počínaje doplňkem daného uzlu a poté kontrolou, zda lze některý z těchto pohybů převést na standardní úplnou trianulaci torusu . Čas této metody by měl být třikrát exponenciální, ale experimenty ukazují, že tyto hranice jsou velmi pesimistické a je potřeba mnohem méně Pachnerových tahů [11] .
- Zbytková konečnost grupy uzlů (která vyplývá z geometrizace Hakenových variet ) dává algoritmus - zkontrolujeme, zda grupa obsahuje necyklickou skupinu konečných faktorů. Tato myšlenka je použita v Kuperbergově důkazu, že problém nevázání patří do třídy co-NP.
- Floerova homologie uzlu definuje rod uzlu, který je 0 právě tehdy, když je uzel triviální. Lze vypočítat kombinatorickou verzi Floerovy homologie uzlu [12] .
- Khovanovova homologie definuje triviálnost uzlu podle výsledků Cronheimera a Mrovky [13] . Složitost Khovanovovy homologie je přinejmenším stejná jako u #P-těžkého problému výpočtu Jonesova polynomu , ale lze ji vypočítat pomocí Bar-Nathanova algoritmu a programu [14] . Bar-Nathan nepodává rigorózní analýzu svého algoritmu, ale heuristicky předpokládá, že algoritmus je exponenciální v šířce dráhy grafu diagramu průniku, což je naopak nejvýše druhá odmocnina z počtu průniků (s určitým faktorem ).
Studium složitosti těchto algoritmů aktivně pokračuje.
Viz také
Poznámky
- ↑ Hass, Lagarias, Pippenger, 1999 .
- ↑ Hara, Tani, Yamamoto, 2005 .
- ↑ Uvedeno jako "soukromá komunikace" [15] v seznamu citací Kuperbergova článku (Kuperberg, 2014).
- ↑ Kuperberg, 2014 .
- ↑ Kawarabayashi, Kreutzer, Mohar, 2010 .
- ↑ Ladd, Kavraki, 2004 .
- ↑ Burton, 2011a .
- ↑ Birman, Hirsch, 1998 .
- ↑ Lackenby, 2015 .
- ↑ Mijatovic, 2005 .
- ↑ Burton, 2011b .
- ↑ Manolescu, Ozsváth, Sarkar, 2009 .
- ↑ Kronheimer, Mrowka, 2011 .
- ↑ Bar-Natan, 2007 .
Literatura
- Dror Bar-Natan. Rychlé výpočty homologie Khovanov // Journal of Knot Theory and Its Ramifications . - 2007. - T. 16 , no. 3 . - S. 243-255 . - doi : 10.1142/S0218216507005294 . - arXiv : math.GT/0606318 .
- Joan S. Birman, Michael Hirsch. Nový algoritmus pro rozpoznávání neuzlů // Geometrie a topologie . - 1998. - T. 2 . - S. 178-220 . - doi : 10.2140/gt.1998.2.175 .
- Benjamin A. Burton. Maximální přípustné plochy a asymptotické hranice pro prostor řešení normálních ploch // Journal of Combinatorial Theory . — 2011a. - T. 118 , č.p. 4 . - S. 1410-1435 . - doi : 10.1016/j.jcta.2010.12.011 . - arXiv : 1004.2605 .
- Benjamin Burton. Proč. 27. sympozium ACM o počítačové geometrii . — 2011b. - S. 153-162. - doi : 10.1145/1998196.1998220 .
- Wolfgang Haken. Theorie der Normalflächen // Acta Mathematica . - 1961. - T. 105 . - S. 245-375 . - doi : 10.1007/BF02559591 .
- Masao Hara, Seiichi Tani, Makoto Yamamoto. Proč. 16. sympozium ACM-SIAM o diskrétních algoritmech (SODA '05) . - 2005. - S. 359-364.
- Joel Hass, Jeffrey C. Lagarias, Nicholas Pippenger. Výpočetní složitost problémů s uzly a spoji // Journal of the ACM . - 1999. - T. 46 , no. 2 . - S. 185-211 . - doi : 10.1145/301970.301971 . - arXiv : math/9807016 .
- Joel Hass, Jeffrey C. Lagarias, Nicholas Pippenger. Počet Reidemeisterových tahů potřebných pro rozuzlení // Journal of the American Mathematical Society . - 2001. - T. 14 , no. 2 . - S. 399-428 . - doi : 10.1090/S0894-0347-01-00358-7 .
- Ken-ichi Kawarabayashi, Stephan Kreutzer, Bojan Mohar. Proč. ACM Symposium on Computational Geometry (SoCG '10) . - 2010. - S. 97-106. - doi : 10.1145/1810959.1810975 .
- Peter Kronheimer, Tomasz Mrowka. Khovanovova homologie je neznámý detektor // Publications Mathématiques de l'IHÉS . - 2011. - T. 113 , č.p. 1 . - S. 97-208 . - doi : 10.1007/s10240-010-0030-y . - arXiv : 1005.4346 .
- Greg Kuperberg. Zauzlenost je v NP, modulo GRH // Pokroky v matematice . - 2014. - T. 256 . - S. 493-506 . - doi : 10.1016/j.aim.2014.01.007 . - arXiv : 1112.0845 .
- Marc Lackenby. Polynomiální horní hranice na Reidemeister se pohybuje // Annals of Mathematics. - 2015. - T. 182 , č.p. 2 . - S. 491-564 . doi : 10.4007 / anals.2015.182.2.3 . - arXiv : 1302.0180 .
- Andrew M. Ladd, Lydia E. Kavraki. Algoritmické základy robotiky 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. Kombinatorický popis Floerovy homologie // Annals of Mathematics . - 2009. - T. 169 , č.p. 2 . - S. 633-660 . - doi : 10.4007/annals.2009.169.633 . — arXiv : math/0607691 .
- Aleksandar Mijatovič. Jednoduché struktury uzlových doplňků // Mathematical Research Letters. - 2005. - T. 12 , no. 6 . - S. 843-856 . - doi : 10.4310/mrl.2005.v12.n6.a6 . — arXiv : math/0306117 .
Odkazy