Rozuzlovací problém - Unknotting problem

Question, Web Fundamentals.svgNevyřešený problém v matematice:
Lze uzly rozpoznat v polynomiálním čase?
(více nevyřešených úloh z matematiky)
Dva jednoduché diagramy unknotu
Složitý unknot diagram od Morwen Thistlethwaite

v matematika, rozuzlovací problém je problém algoritmicky uznává rozepnout, vzhledem k určité reprezentaci uzlu, např. a uzlový diagram. Existuje několik typů rozuzlovacích algoritmů. Hlavní nevyřešenou výzvou je zjistit, zda problém připouští a polynomiální čas algoritmus; to znamená, zda problém spočívá ve třídě složitosti P.

Výpočetní složitost

První kroky k určení výpočetní složitosti byly podniknuty k prokázání, že problém je ve větších třídách složitosti, které obsahují třídu P. Použitím normální povrchy popsat Seifertovy povrchy daného uzlu, Hass, Lagarias & Pippenger (1999) ukázal, že problém s rozuzlením je ve třídě složitosti NP. Hara, Tani a Yamamoto (2005) tvrdil slabší výsledek, že unknotting je v AM ∩ co-AM; později však toto tvrzení odvolali.[1] V roce 2011, Greg Kuperberg prokázal, že (za předpokladu zobecněná Riemannova hypotéza ) problém s rozuzlením je v co-NP,[2] a v roce 2016 Marc Lackenby poskytl bezpodmínečný důkaz o členství v co-NP.[3]

Unknotting problém má stejnou výpočetní složitost jako testování, zda vložení neorientovaný graf v Euklidovský prostor je bez propojení.[4]

Jeden z Ochiaiho unknotů se 139 vrcholy[5]například byl počítačem původně zauzlen za 108 hodin[6], ale tento čas byl u novějšího výzkumu zkrácen na 10 minut.[7]

Rozuzlovací algoritmy

Je založeno na několika algoritmech řešících problém s rozuzlováním Haken teorie o normální povrchy:

  • Hakenův algoritmus používá teorii normálních povrchů k nalezení disku, jehož hranicí je uzel. Haken původně použil tento algoritmus, aby ukázal, že rozuzlování je rozhodující, ale podrobněji neanalyzoval jeho složitost.
  • Hass, Lagarias a Pippenger ukázali, že množina všech normálních ploch může být reprezentována celočíselnými body v polyedrický kužel a že povrch svědčící o bezuzlovosti křivky (pokud existuje) lze vždy najít na jednom z extrémních paprsků tohoto kužele. Proto, metody výčtu vrcholů lze použít k vypsání všech extrémních paprsků a testování, zda některý z nich odpovídá ohraničujícímu disku uzlu. Hass, Lagarias a Pippenger touto metodou ukázali, že unknottedness je v NP; pozdější vědci jako např Burton (2011a) zdokonalili svou analýzu a ukázali, že tento algoritmus může být užitečný (i když ne polynomiálním časem), jehož složitost je jednotlivě exponenciální funkcí nízkého řádu počtu přechodů.
  • Algoritmus Birman & Hirsch (1998) používá opletení opletení, poněkud odlišný typ struktury než normální povrch. Aby však mohli analyzovat jeho chování, vrátí se k normální teorii povrchu.

Mezi další přístupy patří:

  • Počet Reidemeister se pohybuje potřeba změnit unknotový diagram na standardní unknotový diagram je maximálně polynomiální v počtu křížení.[8] Hledání brutální síly pro všechny sekvence pohybů Reidemeister proto může detekovat unknottedness v exponenciálním čase.
  • Podobně jakékoli dvě triangulace stejné uzlový doplněk mohou být spojeny posloupností Pachner se pohybuje délky maximálně dvojnásobně exponenciální v počtu přejezdů.[9] Proto je možné určit, zda je uzel uzlem, testováním všech sekvencí Pachnerových tahů této délky, počínaje komplementem daného uzlu a určením, zda některý z nich transformuje komplement do standardní triangulace a pevný torus. Čas pro tuto metodu by byl trojnásobně exponenciální; experimentální důkazy však naznačují, že tato vazba je velmi pesimistická a že je zapotřebí mnohem méně Pachnerových tahů.[10]
  • Žádný prezentace oblouku uzlu lze monotónně zjednodušit na minimální pomocí elementárních pohybů.[11] Hledání hrubou silou mezi všemi prezentacemi oblouku, které nemají větší složitost, tedy dává jednoexponenciální algoritmus pro problém bez uzlů.
  • Zbytková konečnost z skupina uzlů (což vyplývá z geometrizace z Haken potrubí ) dává algoritmus: zkontrolujte, zda skupina má necyklický konečný skupinový kvocient. Tato myšlenka se používá ve výsledku Kuperberga, že problém s rozuzlením je v co-NP.
  • Homologie uzlů Floer uzlu detekuje rod uzlu, což je 0 právě tehdy, je-li uzel rozuzlený. Kombinatorická verze uzlu Floerova homologie umožňuje její výpočet (Manolescu, Ozsváth a Sarkar 2009 ).
  • Khovanovova homologie detekuje rozuzlení podle výsledku Kronheimer a Mrowka.[12] Složitost Khovanovské homologie je přinejmenším stejně vysoká jako u # P-tvrdé problém výpočtu Jonesův polynom, ale lze jej v praxi vypočítat pomocí algoritmu a programu Bar-Natan (2007). Bar-Natan neposkytuje žádnou důslednou analýzu svého algoritmu, ale heuristicky odhaduje, že je v šířka cesty diagramu křížení, který je zase nanejvýš úměrný druhé odmocnině počtu křížení.

Pochopení složitosti těchto algoritmů je aktivním studijním oborem.

Viz také

Poznámky

  1. ^ Uvedeno jako "osobní komunikace" v odkazu [15] ze dne Kuperberg (2014).
  2. ^ Kuperberg (2014)
  3. ^ Lackenby (2016)
  4. ^ Kawarabayashi, Kreutzer & Mohar (2010).
  5. ^ Ochiai, M. (1990). „Netriviální projekce triviálního uzlu“ (PDF). S.M.F. Asterisque. 192: 7–9.
  6. ^ Grzeszczuk, R .; Huang, M .; Kauffman, L. (1997). "Fyzicky založené stochastické zjednodušení matematických uzlů". Transakce IEEE na vizualizaci a počítačové grafice. 3 (3): 262–278. doi:10.1109/2945.620492.
  7. ^ Ladd & Kavraki (2004).
  8. ^ Lackenby (2015).
  9. ^ Mijatović (2005).
  10. ^ Burton (2011b).
  11. ^ Dynnikov (2006).
  12. ^ Kronheimer & Mrowka (2011)

Reference

externí odkazy

  • Složitost Zoo poskytuje informace o třídách složitosti a jejich inkluzních vztazích.