Úkol oddělení

Úkolem rozvázání  je úkolem algoritmického rozpoznání triviálního uzlu , pokud je dáno nějaké znázornění uzlu, to jest diagram uzlu . Existuje několik typů odvazovacích algoritmů. Hlavním nevyřešeným problémem je, zda lze problém vyřešit v polynomiálním čase , tedy zda problém patří do třídy složitosti P.

Výpočetní složitost

První kroky při definování výpočetní složitosti byly učiněny směrem k prokázání, že problém patří ke složitějším třídám složitosti obsahujícím třídu P. Pomocí normálních ploch k popisu Seifertových ploch daného uzlu ukázali Hass, Lagarias a Pippenger [1] že problém rozvázání patří do třídy složitosti NP . Hara, Tani a Yamamoto [2] uvedli, že rozvázání patří do třídy AM ∩ co-AM . Později však svou žádost stáhli [3] . V roce 2011 Greg Kuperberg dokázal, že (za předpokladu, že je zobecněná Riemannova hypotéza pravdivá ) problém nevázání patří do třídy co-NP [4] .

Problém untie má stejnou výpočetní složitost jako kontrola, zda vložení neorientovaného grafu v euklidovském prostoru není propojené [5] .

Uzel Ochiai, obsahující například 139 vrcholů, byl nejprve rozvázán pomocí počítače za 108 hodin, ale tato doba byla následně zkrácena na 10 minut [6]

Algoritmy zrušení vazby

Některé algoritmy pro řešení problému rozvázání jsou založeny na Hakenově teorii normálních povrchů :

Jiné přístupy:

Studium složitosti těchto algoritmů aktivně pokračuje.

Viz také

Poznámky

  1. ↑ Hass, Lagarias, Pippenger, 1999 .
  2. ↑ Hara, Tani, Yamamoto, 2005 .
  3. ↑ Uvedeno jako "soukromá komunikace" [15] v seznamu citací Kuperbergova článku (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 .

Literatura

Odkazy