Leválasztási feladat
A feloldás feladata egy triviális csomó algoritmikus felismerése, ha adott a csomónak valamilyen reprezentációja, azaz csomódiagram . A feloldó algoritmusoknak többféle típusa létezik. A fő megoldatlan probléma az, hogy a probléma megoldható-e polinomiális időben , azaz a probléma a P összetettségi osztályba
tartozik-e.
Számítási összetettség
A számítási komplexitás meghatározásának első lépései annak bizonyítására irányultak, hogy a probléma összetettebb, P osztályt tartalmazó komplexitási osztályokhoz tartozik. Normál felületek segítségével egy adott csomó Seifert-felületeinek leírására Hass, Lagarias és Pippenger [1] megmutatta . hogy a feloldás problémája az NP . Hara, Tani és Yamamoto [2] kijelentette, hogy a feloldás az AM ∩ co-AM osztályba tartozik . Később azonban visszavonták kérelmüket [3] . 2011 -ben Greg Kuperberg bebizonyította, hogy (feltéve, hogy az általánosított Riemann-hipotézis igaz ) a feloldási probléma a co-NP osztályba tartozik [4] .
A szétválasztási probléma számítási bonyolultsága ugyanolyan bonyolult, mint annak ellenőrzése, hogy egy irányítatlan gráf euklideszi térbe való beágyazása nem kapcsolódik -e [5] .
A 139 csúcsot tartalmazó ochiai csomót például először számítógéppel 108 óra alatt oldották fel, de ezt az időt később 10 percre csökkentették [6]
Feloldó algoritmusok
Egyes algoritmusok a feloldási probléma megoldására a normál felületek Haken -elméletén :
- A Haken-algoritmus a normál felületek elméletét használja egy olyan korong megtalálásához, amelynek határa csomós. Haken eredetileg ezzel az algoritmussal mutatta be, hogy a feloldási probléma megoldható, de nem elemezte részletesen az algoritmus számítási bonyolultságát.
- Hass, Lagarias és Pippenger megmutatta, hogy az összes normálfelület halmaza egész pontként ábrázolható egy poliéderkúpban , és hogy egy görbe (ha van ilyen) feloldásának lehetőségét jelző felület mindig megtalálható az egyik görbén. ennek a kúpnak a szélsőséges sugarai. Így az csúcsfelsorolási módszerek használhatók az összes élsugár számbavételére és annak ellenőrzésére, hogy csomózott lemezhatárok-e. Hass, Lagarias és Pippenger ezzel a módszerrel kimutatta, hogy a feloldás megtalálása az NP osztályba tartozik. Későbbi kutatók, mint például Barton [7] , továbbfejlesztették elemzésüket azzal, hogy kimutatták, hogy ez az algoritmus alacsony rendű exponenciális komplexitás mellett is hasznos lehet (a metszéspontok számának függvényében).
- Birman és Hirsch algoritmusa [8] egy fonatköteget használ , amely kissé eltér a normál felülettől. Viselkedésük elemzéséhez azonban visszatértek a normál felületek elméletéhez.
Egyéb megközelítések:
- A triviális csomódiagram szabványos formába hozásához szükséges Reidemeister mozdulatok száma legfeljebb polinom a metszéspontok számában [9] . Ezért az összes Reidemeister-mozdulat teljes keresése exponenciális idő alatt képes kimutatni a csomó triviális voltát.
- Hasonlóképpen, ugyanannak a csomópont-komplementernek bármely két háromszögelése összekapcsolható Pachner-mozgások sorozatával, amelyek hossza legfeljebb kétszerese a metszéspontok számának exponenciálisának [10] . Így megállapítható, hogy egy csomó triviális-e, ha ellenőrizzük a Puchner ilyen hosszúságú mozdulatainak sorozatait, kezdve egy adott csomó komplementerével, majd ellenőrizzük, hogy ezek közül a mozgások bármelyike átalakítható-e szabványos teljes tórusz -trianulációvá . Ennek a módszernek az ideje háromszoros exponenciális, de a kísérletek azt mutatják, hogy ezek a határok nagyon pesszimisták, és sokkal kevesebb Pachner-mozdulat szükséges [11] .
- A csomócsoport maradék végessége (ami a Haken-sokaságok geometrizálásából következik ) ad egy algoritmust - ellenőrizzük, hogy a csoport tartalmaz-e nem ciklikus véges tényezős csoportot. Ezt az elképzelést használja Kuperberg annak bizonyítására, hogy a feloldási probléma a co-NP osztályba tartozik.
- A csomó Floer homológiája határozza meg a csomó nemzetségét, amely akkor és csak akkor 0, ha a csomó triviális. A csomó Floer-homológiájának kombinatorikus változata kiszámítható [12] .
- Khovanov homológiája meghatározza a csomó trivialitását Cronheimer és Mrovka [13] eredményei alapján . A Khovanov-homológia összetettsége legalább megegyezik a Jones-polinom számításának #P-kemény problémájával, de a Bar-Nathan algoritmus és program segítségével kiszámítható [14] . Bar-Nathan nem ad szigorú elemzést az algoritmusáról, hanem heurisztikusan feltételezi, hogy az algoritmus exponenciális a metszéspontdiagram gráf útvonalában , ami viszont legfeljebb a metszéspontok számának négyzetgyöke (valamilyen tényezővel ).
Ezen algoritmusok összetettségének vizsgálata aktívan folyamatban van.
Lásd még
Jegyzetek
- ↑ Hass, Lagarias, Pippenger, 1999 .
- ↑ Hara, Tani, Yamamoto, 2005 .
- ↑ "Privát kommunikáció" [15] néven említik Kuperberg cikkének idézőlistájában (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 .
Irodalom
- Dror Bar-Natan. Gyors Khovanov-homológia-számítások // Journal of Knot Theory and Its Armifications . - 2007. - T. 16 , sz. 3 . - S. 243-255 . - doi : 10.1142/S0218216507005294 . - arXiv : math.GT/0606318 .
- Joan S. Birman, Michael Hirsch. Egy új algoritmus az unknot felismerésére // Geometria és topológia . - 1998. - T. 2 . - S. 178-220 . - doi : 10.2140/gt.1998.2.175 .
- Benjamin A. Burton. Maximálisan megengedhető lapok és aszimptotikus határok a normál felületi megoldástérhez // Journal of Combinatorial Theory . — 2011a. - T. 118 , sz. 4 . - S. 1410-1435 . - doi : 10.1016/j.jcta.2010.12.011 . - arXiv : 1004.2605 .
- Benjamin Burton. Proc. 27. ACM Szimpózium a Számítógépes Geometriáról . — 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 szimpózium a diszkrét algoritmusokról (SODA '05) . - 2005. - S. 359-364.
- Joel Hass, Jeffrey C. Lagarias, Nicholas Pippenger. A csomó- és linkproblémák számítási összetettsége // Journal of the ACM . - 1999. - T. 46 , sz. 2 . - S. 185-211 . - doi : 10.1145/301970.301971 . - arXiv : math/9807016 .
- Joel Hass, Jeffrey C. Lagarias, Nicholas Pippenger. A csomózás megszüntetéséhez szükséges Reidemeister-mozdulatok száma // Journal of the American Mathematical Society . - 2001. - T. 14 , sz. 2 . - S. 399-428 . - doi : 10.1090/S0894-0347-01-00358-7 .
- Ken-ichi Kawarabayashi, Stephan Kreutzer, Bojan Mohar. Proc. ACM Szimpózium a Számítógépes Geometriáról (SoCG '10) . - 2010. - S. 97-106. - doi : 10.1145/1810959.1810975 .
- Peter Kronheimer, Tomasz Mrowka. A Khovanov homology is an unnot-detector // Publications Mathématiques de l'IHÉS . - 2011. - T. 113 , sz. 1 . - S. 97-208 . - doi : 10.1007/s10240-010-0030-y . - arXiv : 1005.4346 .
- Greg Kuperberg. A csomózottság NP-ben van, modulo GRH // Advances in Mathematics . - 2014. - T. 256 . - S. 493-506 . - doi : 10.1016/j.aim.2014.01.007 . - arXiv : 1112.0845 .
- Marc Lackenby. A Reidemeister-mozgások polinomiális felső korlátja // Annals of Mathematics. - 2015. - T. 182 , sz. 2 . - S. 491-564 . doi : 10.4007 / annals.2015.182.2.3 . - arXiv : 1302.0180 .
- Andrew M. Ladd, Lydia E. Kavraki. A robotika algoritmikus alapjai 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 csomó Floer homológia kombinatorikus leírása // Annals of Mathematics . - 2009. - T. 169 , sz. 2 . - S. 633-660 . - doi : 10.4007/annals.2009.169.633 . — arXiv : math/0607691 .
- Aleksandar Mijatovic. Csomókomplementerek egyszerű szerkezetei // Mathematical Research Letters. - 2005. - T. 12 , sz. 6 . - S. 843-856 . - doi : 10.4310/mrl.2005.v12.n6.a6 . — arXiv : math/0306117 .
Linkek