Afkoblingsopgave
Opgaven med at løsne er opgaven med algoritmisk genkendelse af en triviel knude , hvis der er givet en eller anden repræsentation af knuden, det vil sige et knudediagram . Der er flere typer af ubindende algoritmer. Det vigtigste uløste problem er, om problemet kan løses i polynomiel tid , det vil sige om problemet tilhører kompleksitetsklassen
P.
Beregningsmæssig kompleksitet
De første skridt til at definere beregningskompleksitet blev taget for at bevise, at problemet tilhører mere komplekse kompleksitetsklasser, der indeholder klassen P. Ved at bruge normale overflader til at beskrive Seifert-overfladerne af en given knude, viste Hass, Lagarias og Pippenger [1] at problemet med afbinding hører til NP . Hara, Tani og Yamamoto [2] udtalte, at afbinding hører til klassen AM ∩ co-AM . Senere trak de dog deres ansøgning tilbage [3] . I 2011 beviste Greg Kuperberg at (forudsat at den generaliserede Riemann-hypotese er sand ) hører det ubindende problem til co-NP-klassen [4] .
Løsningsproblemet har samme beregningsmæssige kompleksitet som at kontrollere, om en indlejring af en ikke-rettet graf i det euklidiske rum er afkoblet [5] .
Ochiai-knuden, der for eksempel indeholdt 139 hjørner, blev først løst ved hjælp af en computer i 108 timer, men denne tid blev efterfølgende reduceret til 10 minutter [6]
Ubindende algoritmer
Nogle algoritmer til løsning af afbindingsproblemet er baseret på Haken- teorien om normale overflader :
- Hakens algoritme bruger teorien om normale overflader til at finde en skive, hvis grænse er knyttet. Haken brugte oprindeligt denne algoritme til at vise, at det ubindende problem er løseligt, men han analyserede ikke algoritmens beregningsmæssige kompleksitet i detaljer.
- Hass, Lagarias og Pippenger viste, at sættet af alle normale overflader kan repræsenteres som heltalspunkter i en polyedrisk kegle , og at en overflade, der indikerer muligheden for at afbinde en kurve (hvis der er en), altid kan findes på en af ekstreme stråler af denne kegle. Således kan vertex-optællingsmetoderne bruges til at opregne alle kantstråler og kontrollere, om de er knudrede skivegrænser. Hass, Lagarias og Pippenger brugte denne metode til at vise, at det at finde en afbinding hører til klassen NP. Senere forskere som Barton [7] forbedrede deres analyse ved at vise, at denne algoritme kan være nyttig med lav ordens eksponentiel kompleksitet (som funktion af antallet af skæringspunkter).
- Birman og Hirschs algoritme [8] bruger et fletbundt , en lidt anderledes struktur end en normal overflade. Men for at analysere deres adfærd vendte de tilbage til teorien om normale overflader.
Andre tilgange:
- Antallet af Reidemeister-træk , der kræves for at bringe det trivielle knudediagram til standardformen, er højst polynomium i antallet af skæringspunkter [9] . Derfor kan en komplet søgning af alle Reidemeister-træk opdage trivialiteten af en knude i eksponentiel tid.
- Tilsvarende kan enhver to triangulariseringer af det samme nodekomplement forbindes af en sekvens af Pachner-bevægelser af længde, der ikke er mere end dobbelt så stor som eksponentiel af antallet af skæringspunkter [10] . Således kan man afgøre, om en knude er triviel ved at kontrollere sekvenser af Puchner-bevægelser af den længde, begyndende med komplementet til en given knude, og derefter kontrollere, om nogen af disse træk kan konverteres til en standard fuld torus -trianulation . Tidspunktet for denne metode bør være tre gange eksponentiel, men eksperimenter viser, at disse grænser er meget pessimistiske, og langt færre Pachner-træk er nødvendige [11] .
- Den resterende endelighed af knudegruppen (som følger af geometriseringen af Haken-manifolds ) giver en algoritme - vi tjekker om gruppen indeholder en ikke-cyklisk endelig faktorgruppe. Denne idé bruges i Kuperbergs bevis på, at det uforpligtende problem tilhører co-NP-klassen.
- Floer-homologien af en knude definerer en knudes slægt, som er 0, hvis og kun hvis knuden er triviel. En kombinatorisk version af Floer-homologien af en knude kan beregnes [12] .
- Khovanovs homologi definerer knudens trivialitet i henhold til resultaterne af Cronheimer og Mrovka [13] . Kompleksiteten af Khovanov-homologien er i det mindste den samme som for #P-hard problem med beregning af Jones-polynomiet , men den kan beregnes ved hjælp af Bar-Nathan-algoritmen og -programmet [14] . Bar-Nathan giver ikke en streng analyse af sin algoritme, men antager heuristisk, at algoritmen er eksponentiel i stibredden af skæringsdiagramgrafen, som igen er højst kvadratroden af antallet af skæringspunkter (med en eller anden faktor) ).
Undersøgelsen af kompleksiteten af disse algoritmer er aktivt i gang.
Se også
Noter
- ↑ Hass, Lagarias, Pippenger, 1999 .
- ↑ Hara, Tani, Yamamoto, 2005 .
- ↑ Nævnt som "privat kommunikation" [15] i citatlisten til Kuperbergs artikel (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 .
Litteratur
- Dror Bar-Natan. Hurtige Khovanov-homologiberegninger // 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. En ny algoritme til at genkende uknoden // Geometri og topologi . - 1998. - T. 2 . - S. 178-220 . - doi : 10.2140/gt.1998.2.175 .
- Benjamin A. Burton. Maksimalt tilladte flader og asymptotiske grænser for det normale overfladeløsningsrum // 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 om beregningsgeometri . - 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 om diskrete algoritmer (SODA '05) . - 2005. - S. 359-364.
- Joel Hass, Jeffrey C. Lagarias, Nicholas Pippenger. Den beregningsmæssige kompleksitet af knude- og linkproblemer // 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. Antallet af Reidemeister-træk, der skal til for at løsne sig // 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-homologi er en uknob-detektor // 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 er 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 polynomisk øvre grænse på Reidemeister flytter // Annals of Mathematics. - 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. 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 beskrivelse af knude Floer homologi // Annals of Mathematics . - 2009. - T. 169 , no. 2 . - S. 633-660 . - doi : 10.4007/annals.2009.169.633 . — arXiv : math/0607691 .
- Aleksandar Mijatovic. Simple strukturer af knudekomplementer // Mathematical Research Letters. - 2005. - T. 12 , no. 6 . - S. 843-856 . - doi : 10.4310/mrl.2005.v12.n6.a6 . — arXiv : math/0306117 .
Links