Irrotustehtävä

Purkamisen tehtävä on triviaalin solmun  algoritminen tunnistus, jos solmusta annetaan jokin esitys, eli solmukaavio . Sidotusten purkamisalgoritmeja on useita. Pääasiallinen ratkaisematon ongelma on se, voidaanko ongelma ratkaista polynomiajassa , eli kuuluuko ongelma monimutkaisuusluokkaan P.

Laskennallinen monimutkaisuus

Ensimmäiset askeleet laskennallisen monimutkaisuuden määrittelyssä otettiin sen osoittamiseksi, että ongelma kuuluu monimutkaisempiin kompleksisuusluokkiin, jotka sisältävät luokan P. Käyttämällä normaaleja pintoja kuvaamaan tietyn solmun Seifert-pintoja , Hass, Lagarias ja Pippenger [1] osoittivat . että sidonnaisuuden purkamisongelma kuuluu NP . Hara, Tani ja Yamamoto [2] totesivat, että irrottaminen kuuluu luokkaan AM ∩ co-AM . Myöhemmin he kuitenkin peruuttivat hakemuksensa [3] . Vuonna 2011 Greg Kuperberg osoitti, että (olettaen , että yleistetty Riemmann-hypoteesi pitää paikkansa ) irtoamisongelma kuuluu co-NP-luokkaan [4] .

Irrotusongelmalla on sama laskennallinen monimutkaisuus kuin sen tarkistaminen, onko ohjaamattoman graafin upottaminen euklidiseen avaruuteen linkittämätön [5] .

Esimerkiksi 139 kärkeä sisältävä Ochiai-solmu purettiin ensin tietokoneen avulla 108 tunnissa, mutta tämä aika lyhennettiin myöhemmin 10 minuuttiin [6]

Sidontaalgoritmit

Eräät algoritmit purkamisongelman ratkaisemiseksi perustuvat Hakenin teoriaan normaaleista pinnoista :

• Hakenin algoritmi käyttää normaalipintojen teoriaa löytääkseen levyn, jonka raja on solmuinen. Haken käytti alun perin tätä algoritmia osoittamaan, että sitomisongelma on ratkaistavissa, mutta hän ei analysoinut algoritmin laskennallista monimutkaisuutta yksityiskohtaisesti.
• Hass, Lagarias ja Pippenger osoittivat, että kaikkien normaalien pintojen joukko voidaan esittää kokonaislukupisteinä monitahoisessa kartiossa ja että pinta, joka osoittaa mahdollisuutta irrottaa käyrä (jos sellainen on), löytyy aina jostakin tämän kartion äärimmäisiä säteitä. Siten vertex numeration -menetelmiä voidaan käyttää kaikkien reunasäteiden luetteloimiseen ja tarkistamiseen, ovatko ne solmuisia levyrajoja. Hass, Lagarias ja Pippenger käyttivät tätä menetelmää osoittaakseen, että irrotuksen löytäminen kuuluu luokkaan NP. Myöhemmin tutkijat, kuten Barton [7] , paransivat analyysiään osoittamalla, että tämä algoritmi voi olla hyödyllinen alhaisen eksponentiaalisen monimutkaisuuden kanssa (leikkausten lukumäärän funktiona).
• Birmanin ja Hirschin algoritmi [8] käyttää punoskimppua , joka on hieman erilainen rakenne kuin normaali pinta. Kuitenkin analysoidakseen käyttäytymistään he palasivat normaalien pintojen teoriaan.

Muita lähestymistapoja:

• Triviaalisolmukaavion saattamiseksi vakiomuotoon tarvittavien Reidemeister -liikkeiden määrä on korkeintaan polynomi leikkauspisteiden määrässä [9] . Siksi kaikkien Reidemeisterin liikkeiden täydellinen haku voi havaita solmun triviaalisuuden eksponentiaalisessa ajassa.
• Samoin mitkä tahansa kaksi saman solmukomplementin kolmiota voidaan yhdistää Pachnerin liikkeiden sekvenssillä, jonka pituus on enintään kaksi kertaa leikkauspisteiden lukumäärän eksponentiaali [10] . Siten voidaan määrittää, onko solmu triviaali, tarkistamalla tämän pituisten Puchnerin liikkeiden sekvenssit alkaen tietyn solmun komplementista ja tarkistamalla sitten, voidaanko jokin näistä liikkeistä muuntaa tavalliseksi täystorustrianulaatioksi . Tämän menetelmän ajan tulisi olla kolme kertaa eksponentiaalinen, mutta kokeet osoittavat, että nämä rajat ovat hyvin pessimistisiä ja tarvitaan paljon vähemmän Pachnerin liikkeitä [11] .
• Solmuryhmän jäännösääreisyys ( joka seuraa Hakenin monistojen geometrisoinnista ) antaa algoritmin - tarkistamme, sisältääkö ryhmä ei-syklisen äärellisen tekijäryhmän. Tätä ajatusta käytetään Kuperbergin todistuksessa siitä, että sitomisongelma kuuluu co-NP-luokkaan.
• Solmun Floer-homologia määrittelee solmun suvun, joka on 0, jos ja vain jos solmu on triviaali. Solmun Floer-homologian kombinatorinen versio voidaan laskea [12] .
• Khovanovin homologia määrittelee solmun triviaalisuuden Cronheimerin ja Mrovkan [13] tulosten mukaan . Khovanov-homologian monimutkaisuus on vähintään sama kuin Jones-polynomin laskemisen #P-hard ongelma , mutta se voidaan laskea käyttämällä Bar-Nathan-algoritmia ja -ohjelmaa [14] . Bar-Nathan ei anna tarkkaa analyysiä algoritmistaan, vaan olettaa heuristisesti, että algoritmi on eksponentiaalinen leikkauskaavion graafin polun leveydellä , joka puolestaan ​​on korkeintaan leikkauspisteiden lukumäärän neliöjuuri (jollakin tekijällä ).

Näiden algoritmien monimutkaisuuden tutkimus jatkuu aktiivisesti.

Katso myös

• Algoritminen topologia
• Irrota numero (solmuteoria)

Muistiinpanot

1. ↑ Hass, Lagarias, Pippenger, 1999 .
2. ↑ Hara, Tani, Yamamoto, 2005 .
3. ↑ Mainittu "yksityiseksi viestintäksi" [15] Kuperbergin artikkelin lainausluettelossa (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. ↑ Mijatovic, 2005 .
11. ↑ Burton, 2011b .
12. ↑ Manolescu, Ozsváth, Sarkar, 2009 .
13. ↑ Kronheimer, Mrowka, 2011 .
14. ↑ Bar-Natan, 2007 .

Kirjallisuus

• Dror Bar-Natan. Nopeat Khovanov-homologialaskelmat // 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. Uusi algoritmi unnotin tunnistamiseen // Geometria ja topologia . - 1998. - T. 2 . - S. 178-220 . - doi : 10.2140/gt.1998.2.175 .
• Benjamin A. Burton. Normaalin pintaratkaisuavaruuden suurimmat sallitut kasvot ja asymptoottiset rajat  // Journal of Combinatorial Theory . – 2011a. - T. 118 , no. 4 . - S. 1410-1435 . - doi : 10.1016/j.jcta.2010.12.011 . - arXiv : 1004.2605 .
• Benjamin Burton. Proc. 27. ACM Symposium on Computational Geometry . – 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. Proc. 16. ACM-SIAM-symposium diskreetistä algoritmista (SODA '05) . - 2005. - S. 359-364.
• Joel Hass, Jeffrey C. Lagarias, Nicholas Pippenger. Solmu- ja linkkiongelmien laskennallinen monimutkaisuus // 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. Reidemeisterin liikkeiden määrä, joka tarvitaan merkintöjen poistamiseen // 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. Proc. ACM Symposium on Computational Geometry (SoCG '10) . - 2010. - S. 97-106. - doi : 10.1145/1810959.1810975 .
• Peter Kronheimer, Tomasz Mrowka. Khovanov-homologia on unnot-detector // Publications Mathématiques de l'IHÉS . - 2011. - T. 113 , no. 1 . - S. 97-208 . - doi : 10.1007/s10240-010-0030-y . - arXiv : 1005.4346 .
• Greg Kuperberg. Knottedness on NP:ssä, modulo GRH // Advances in Mathematics . - 2014. - T. 256 . - S. 493-506 . - doi : 10.1016/j.aim.2014.01.007 . - arXiv : 1112.0845 .
• Marc Lackenby. Reidemeisterin liikkeiden polynomin yläraja  // Matematiikan Annals. - 2015. - T. 182 , no. 2 . - S. 491-564 . doi : 10.4007 / annals.2015.182.2.3 . - arXiv : 1302.0180 .
• Andrew M. Ladd, Lydia E. Kavraki. Robotiikan algoritmiset perusteet 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. Knot Floer -homologian kombinatorinen kuvaus  // Annals of Mathematics . - 2009. - T. 169 , no. 2 . - S. 633-660 . - doi : 10.4007/annals.2009.169.633 . — arXiv : math/0607691 .
• Aleksandar Mijatovic. Solmukomplementtien yksinkertaiset rakenteet // Mathematical Research Letters. - 2005. - T. 12 , no. 6 . - S. 843-856 . - doi : 10.4310/mrl.2005.v12.n6.a6 . — arXiv : math/0306117 .

Linkit

• Complexity Zoo Arkistoitu 27. elokuuta 2019 Wayback Machinessa antaa tietoa monimutkaisuusluokista ja niiden suhteista.