Frikopplingsuppgift

Uppgiften att lossa  är uppgiften att algoritmiskt identifiera en trivial knut om någon representation av knuten ges, det vill säga ett knutdiagram . Det finns flera typer av obindande algoritmer. Det huvudsakliga olösta problemet är om problemet kan lösas i polynomtid , det vill säga om problemet tillhör komplexitetsklassen P.

Beräkningskomplexitet

De första stegen för att definiera beräkningskomplexitet togs för att bevisa att problemet tillhör mer komplexa komplexitetsklasser som innehåller klassen P. Genom att använda normala ytor för att beskriva Seifert-ytorna för en given knut visade Hass, Lagarias och Pippenger [1] att problemet med obindning tillhör NP . Hara, Tani och Yamamoto [2] uppgav att obindning tillhör klassen AM ∩ co-AM . Senare drog de dock tillbaka sin ansökan [3] . År 2011 bevisade Greg Kuperberg att (förutsatt att den generaliserade Riemann-hypotesen är sann ) det obindande problemet tillhör co-NP-klassen [4] .

Lösningsproblemet har samma beräkningskomplexitet som att kontrollera om en inbäddning av en oriktad graf i det euklidiska rymden är urkopplad [5] .

Ochiai-knuten, som innehåller 139 hörn, till exempel, lossades först med en dator på 108 timmar, men denna tid reducerades sedan till 10 minuter [6]

Avbindande algoritmer

Vissa algoritmer för att lösa uppkopplingsproblemet är baserade på Haken- teorin om normala ytor :

• Hakens algoritm använder teorin om normala ytor för att hitta en skiva vars gräns är knuten. Haken använde ursprungligen denna algoritm för att visa att det obindande problemet är lösbart, men han analyserade inte algoritmens beräkningskomplexitet i detalj.
• Hass, Lagarias och Pippenger visade att mängden av alla normala ytor kan representeras som heltalspunkter i en polyedrisk kon , och att en yta som indikerar möjligheten att avbinda en kurva (om det finns en) alltid kan hittas på en av de extrema strålar från denna kon. Således kan vertexuppräkningsmetoderna användas för att räkna upp alla kantstrålar och kontrollera om de är knutna skivgränser. Hass, Lagarias och Pippenger använde den här metoden för att visa att hitta en lösgöring tillhör klassen NP. Senare forskare som Barton [7] förbättrade sin analys genom att visa att denna algoritm kan vara användbar med låg ordnings exponentiell komplexitet (som en funktion av antalet skärningspunkter).
• Birman och Hirschs algoritm [8] använder en flätbunt , en något annorlunda struktur än en normal yta. Men för att analysera deras beteende återgick de till teorin om normala ytor.

Andra tillvägagångssätt:

• Antalet Reidemeister-drag som krävs för att få det triviala knutdiagrammet till standardformen är som mest polynom i antalet skärningar [9] . Därför kan en fullständig sökning av alla Reidemeister-drag upptäcka trivialiteten av en knut i exponentiell tid.
• På liknande sätt kan två godtyckliga triangulariseringar av samma nodkomplement kopplas samman med en sekvens av Pachner-rörelser av längd som inte är mer än två gånger exponentiellt av antalet skärningar [10] . Således kan man avgöra om en knut är trivial genom att kontrollera sekvenser av Puchner-rörelser av den längden, börja med komplementet till en given knut, och sedan kontrollera om något av dessa drag kan konverteras till en standardfull torus -trianulering . Tiden för denna metod bör vara tre gånger exponentiell, men experiment visar att dessa gränser är mycket pessimistiska och mycket färre Pachner-drag behövs [11] .
• Den resterande ändligheten av knutgruppen (som följer av geometriseringen av Haken manifolds ) ger en algoritm - vi kontrollerar om gruppen innehåller en icke-cyklisk finit faktorgrupp. Denna idé används i Kuperbergs bevis på att det obindande problemet tillhör co-NP-klassen.
• Floer-homologin för en knut definierar släktet för en knut, som är 0 om och endast om knuten är trivial. En kombinatorisk version av Floer-homologin av en knut kan beräknas [12] .
• Khovanovs homologi definierar knutens trivialitet enligt resultaten av Cronheimer och Mrovka [13] . Komplexiteten i Khovanov-homologin är åtminstone densamma som för #P-hårda problemet med att beräkna Jones-polynomet , men det kan beräknas med hjälp av Bar-Nathan-algoritmen och programmet [14] . Bar-Nathan ger ingen rigorös analys av sin algoritm, utan antar heuristiskt att algoritmen är exponentiell i vägbredden för skärningsdiagramgrafen, som i sin tur är högst kvadratroten av antalet korsningar (med någon faktor) ).

Studiet av komplexiteten hos dessa algoritmer pågår aktivt.

Se även

• Algoritmisk topologi
• Lossa nummer (knutteori)

Anteckningar

1. ↑ Hass, Lagarias, Pippenger, 1999 .
2. ↑ Hara, Tani, Yamamoto, 2005 .
3. ↑ Nämnd som "privat kommunikation" [15] i citatlistan till Kuperbergs artikel (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 .

Litteratur

• Dror Bar-Natan. Snabba Khovanov-homologiberäkningar // Journal of Knot Theory and its Ramifications . - 2007. - T. 16 , nr. 3 . - S. 243-255 . - doi : 10.1142/S0218216507005294 . - arXiv : math.GT/0606318 .
• Joan S. Birman, Michael Hirsch. En ny algoritm för att känna igen oknuten // Geometry and Topology . - 1998. - T. 2 . - S. 178-220 . - doi : 10.2140/gt.1998.2.175 .
• Benjamin A. Burton. Maximalt tillåtna ytor och asymptotiska gränser för det normala ytlösningsutrymmet  // Journal of Combinatorial Theory . — 2011a. - T. 118 , nr. 4 . - S. 1410-1435 . - doi : 10.1016/j.jcta.2010.12.011 . - arXiv : 1004.2605 .
• Benjamin Burton. Proc. 27:e ACM-symposiet om beräkningsgeometri . — 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:e ACM-SIAM-symposiet om diskreta algoritmer (SODA '05) . - 2005. - S. 359-364.
• Joel Hass, Jeffrey C. Lagarias, Nicholas Pippenger. Den beräkningsmässiga komplexiteten hos knut- och länkproblem // Journal of the ACM . - 1999. - T. 46 , nr. 2 . - S. 185-211 . - doi : 10.1145/301970.301971 . - arXiv : math/9807016 .
• Joel Hass, Jeffrey C. Lagarias, Nicholas Pippenger. Antalet Reidemeister-drag som behövs för att lösa upp // Journal of the American Mathematical Society . - 2001. - T. 14 , nr. 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-homologi är en oknut-detektor // Publications Mathématiques de l'IHÉS . - 2011. - T. 113 , nr. 1 . - S. 97-208 . - doi : 10.1007/s10240-010-0030-y . - arXiv : 1005.4346 .
• Greg Kuperberg. Knottedness är i NP, modulo GRH // Advances in Mathematics . - 2014. - T. 256 . - S. 493-506 . - doi : 10.1016/j.aim.2014.01.007 . - arXiv : 1112.0845 .
• Marc Lackenby. En polynom övre gräns på Reidemeister flyttar  // Annals of Mathematics. - 2015. - T. 182 , nr. 2 . - S. 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. - 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. En kombinatorisk beskrivning av knut Floer homologi  // Annals of Mathematics . - 2009. - T. 169 , nr. 2 . - S. 633-660 . - doi : 10.4007/annals.2009.169.633 . — arXiv : math/0607691 .
• Aleksandar Mijatovic. Enkla strukturer av knutkomplement // Mathematical Research Letters. - 2005. - T. 12 , nr. 6 . - S. 843-856 . - doi : 10.4310/mrl.2005.v12.n6.a6 . — arXiv : math/0306117 .

Länkar

• Complexity Zoo Arkiverad 27 augusti 2019 på Wayback Machine ger information om komplexitetsklasser och deras relationer.