Sarcina de decuplare

Sarcina dezlegarii  este sarcina recunoașterii algoritmice a unui nod banal dacă este dată o reprezentare a nodului, adică o diagramă a nodului . Există mai multe tipuri de algoritmi de dezlegare. Principala problemă nerezolvată este dacă problema poate fi rezolvată în timp polinomial , adică dacă problema aparține clasei de complexitate P.

Complexitate computațională

Primii pași în definirea complexității computaționale au fost făcuți pentru a demonstra că problema aparține unor clase de complexitate mai complexe care conțin clasa P. Folosind suprafețele normale pentru a descrie suprafețele Seifert ale unui nod dat, Hass, Lagarias și Pippenger [1] au arătat că problema dezlegarii aparţine clasei de complexitate NP . Hara, Tani și Yamamoto [2] au afirmat că dezlegarea aparține clasei AM ∩ co-AM . Ulterior însă și-au retras cererea [3] . În 2011 , Greg Kuperberg a demonstrat că (presupunând că ipoteza Riemann generalizată este adevărată ) problema de legare aparține clasei co-NP [4] .

Problema dezlegare are aceeași complexitate de calcul ca și verificarea dacă o încorporare a unui graf nedirecționat în spațiul euclidian este nelegată [5] .

Nodul Ochiai, care conține 139 de vârfuri, de exemplu, a fost dezlegat mai întâi folosind un computer în 108 ore, dar acest timp a fost ulterior redus la 10 minute [6]

Algoritmi de dezlegare

Unii algoritmi pentru rezolvarea problemei dezlegarii se bazeaza pe teoria Haken a suprafetelor normale :

• Algoritmul lui Haken folosește teoria suprafețelor normale pentru a găsi un disc a cărui limită este înnodată. Haken a folosit inițial acest algoritm pentru a arăta că problema dezlegarii este rezolvabilă, dar nu a analizat complexitatea de calcul a algoritmului în detaliu.
• Hass, Lagarias și Pippenger au arătat că mulțimea tuturor suprafețelor normale poate fi reprezentată ca puncte întregi într-un con poliedric și că o suprafață care indică posibilitatea dezlegarii unei curbe (dacă există una) poate fi întotdeauna găsită pe una dintre razele extreme ale acestui con. Astfel, metodele de enumerare a vârfurilor pot fi folosite pentru a enumera toate razele de margine și pentru a verifica dacă acestea sunt granițe de disc înnodate. Hass, Lagarias și Pippenger au folosit această metodă pentru a arăta că găsirea unei dezlegari aparține clasei NP. Cercetătorii de mai târziu, cum ar fi Barton [7] și-au îmbunătățit analiza, arătând că acest algoritm poate fi util cu o complexitate exponențială de ordin scăzut (în funcție de numărul de intersecții).
• Algoritmul lui Birman și Hirsch [8] folosește un fascicul de împletituri , o structură ușor diferită de o suprafață normală. Cu toate acestea, pentru a le analiza comportamentul, au revenit la teoria suprafețelor normale.

Alte abordări:

• Numărul de mișcări Reidemeister necesare pentru a aduce diagrama nodurilor triviale la forma standard este cel mult polinom în numărul de intersecții [9] . Prin urmare, o căutare completă a tuturor mișcărilor Reidemeister poate detecta trivialitatea unui nod în timp exponențial.
• În mod similar, oricare două triunghiulări ale aceluiași complement de nod pot fi conectate printr-o succesiune de mișcări Pachner de lungime nu mai mare de două ori exponențiala a numărului de intersecții [10] . Astfel, se poate determina dacă un nod este banal verificând secvențele de mișcări Puchner de acea lungime, începând cu complementul unui nod dat și apoi verificând dacă vreuna dintre aceste mișcări poate fi convertită într-o trianulare standard a torusului complet . Timpul acestei metode ar trebui să fie de trei ori exponențial, dar experimentele arată că aceste limite sunt foarte pesimiste și sunt necesare mult mai puține mișcări Pachner [11] .
• Finitudinea reziduală a grupului de noduri (care decurge din geometrizarea varietăților Haken ) dă un algoritm - verificăm dacă grupul conține un grup de factori finiți neciclici. Această idee este folosită în demonstrația lui Kuperberg că problema de legare aparține clasei co-NP.
• Omologia Floer a unui nod definește genul unui nod, care este 0 dacă și numai dacă nodul este banal. O versiune combinatorie a omologiei Floer a unui nod poate fi calculată [12] .
• Omologia lui Khovanov definește trivialitatea nodului conform rezultatelor lui Cronheimer și Mrovka [13] . Complexitatea omologiei lui Khovanov este cel puțin aceeași cu cea a problemei #P-hard de calcul a polinomului Jones , dar poate fi calculată folosind algoritmul și programul Bar-Nathan [14] . Bar-Nathan nu oferă o analiză riguroasă a algoritmului său, dar presupune euristic că algoritmul este exponențial în lățimea de cale a graficului diagramei de intersecție, care, la rândul său, este cel mult rădăcina pătrată a numărului de intersecții (cu un anumit factor ).

Studiul complexității acestor algoritmi este în desfășurare activă.

Vezi și

• Topologie algoritmică
• Dezlegați numărul (teoria nodurilor)

Note

1. ↑ Hass, Lagarias, Pippenger, 1999 .
2. ↑ Hara, Tani, Yamamoto, 2005 .
3. ↑ Menționat ca „comunicare privată” [15] în lista de citări a articolului lui Kuperberg (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 .

Literatură

• Dror Bar-Natan. Calcule rapide de omologie Khovanov // 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. Un nou algoritm pentru recunoașterea deznodării // Geometrie și Topologie . - 1998. - T. 2 . - S. 178-220 . - doi : 10.2140/gt.1998.2.175 .
• Benjamin A. Burton. Fețe maxime admisibile și limite asimptotice pentru spațiul normal de soluție de suprafață  // 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. Al 27-lea Simpozion ACM de Geometrie Computațională . — 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. Al 16-lea Simpozion ACM-SIAM despre algoritmi discreti (SODA '05) . - 2005. - S. 359-364.
• Joel Hass, Jeffrey C. Lagarias, Nicholas Pippenger. Complexitatea de calcul a problemelor de noduri și legături // 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. Numărul de mișcări Reidemeister necesare pentru deznodare // 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. Simpozionul ACM de geometrie computațională (SoCG '10) . - 2010. - S. 97-106. - doi : 10.1145/1810959.1810975 .
• Peter Kronheimer, Tomasz Mrowka. Omologia lui Khovanov este un detector de unknot // 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. Anodarea este în 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. O limită superioară a polinomului pe Reidemeister se mișcă  // Analele matematicii. - 2015. - T. 182 , nr. 2 . - S. 491-564 . doi : 10.4007 / anals.2015.182.2.3 . - arXiv : 1302.0180 .
• Andrew M. Ladd, Lydia E. Kavraki. Fundamentele algoritmice ale roboticii 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. O descriere combinatorie a omologiei nodului Floer  // Annals of Mathematics . - 2009. - T. 169 , nr. 2 . - S. 633-660 . - doi : 10.4007/annals.2009.169.633 . — arXiv : math/0607691 .
• Aleksandar Mijatovic. Structuri simple ale complementelor de noduri // Mathematical Research Letters. - 2005. - T. 12 , nr. 6 . - S. 843-856 . - doi : 10.4310/mrl.2005.v12.n6.a6 . — arXiv : math/0306117 .

Link -uri

• Complexity Zoo Arhivat pe 27 august 2019 la Wayback Machine oferă informații despre clasele de complexitate și relațiile lor.