Czy istnieją teoretyczne sformułowania węzłów NP całkowitych problemów?

Czy istnieją problemy NP pełne (a nawet trudne NP lub NP), które mają dobre właściwości topologiczne do zbadania. Czy problemy NP mają formuły teoretyczne węzłów? Wiemy o wynikach # dotyczących wielomianu Jonesa. Problemy z grafem (osadzanie?), A konkretnie kolorowanie grafów może mieć dobre właściwości teoretyczne węzłów. To pytanie jest otwarte, a wszelkie odniesienia do tego tematu są mile widziane. $P$

ct.category-theory np

— użytkownik3483902
źródło

Odpowiedzi:

Możesz spojrzeć na:

Peter Golbus, Robert W. McGrail, Tomasz Przytycki, Mary Sharac i Aleksandar Chakarov. 2009. Trójkolorowe węzły torusowe są NP-kompletne . W materiałach 47. dorocznej konferencji regionalnej na południowym wschodzie (ACM-SE 47). ACM, Nowy Jork, Nowy Jork, USA, art. 42, 6 stron.

Streszczenie: W pracy przedstawiono metodę powiązania klasy problemów satysfakcji z ograniczeń z trójwymiarowym węzłem. Biorąc węzeł, można zbudować kołek węzła, który jest ogólnie nieskończoną wolną algebrą. Pożądany zbiór problemów wywodzi się ze zbioru niezmienniczych relacji w quandle węzła, stosując teorię, która łączy algebry skończone z problemami satysfakcji z ograniczeń. To pozwala nam opracowywać pojęcia wykonalnych i NP-kompletnych quandles i węzłów. W szczególności pokazujemy, że wszystkie trójkolorowe sęki torusa i wszystkie oprócz maksymalnie 2 nietrywialnych sęków z 10 lub mniejszymi skrzyżowaniami są NP-kompletne.

a także do jego doniosłego sprawozdania:

P. Golbus, RW McGrail, M. Merling, K. Ober, M. Sharac i J. Wood. Klasa problemów z ograniczeniem satysfakcji w węzłach . Raport techniczny nr BARD-CMSC-2008-01, Bard College, 2008.

— Marzio De Biasi
źródło

Istnieje kilka odniesień w pierwszym akapicie

Marc Lackenby. Wielomianowa górna granica ruchów Reidemeister. arXiv: 1302.0180

$\mathbf{NP} \cap \mathbf{coNP}$

Joel Hass, Jeffrey C. Lagarias, Nicholas Pippenger. Złożoność obliczeniowa problemów z węzłami i łączami. J. ACM 46 (1999) 185-211. arXiv: matematyka / 9807016
Greg Kuperberg. Wiązanie jest w NP, modulo GRH. Grudzień 2011 r., Zmieniony w styczniu 2014 r. ArXiv: 1112.0845

$g$

Ian Agol, Joel Hass, William Thurston. 3-MANIFOLD KNOT GENUS jest kompletny NP. STOC 2002. Link do ACM

Interesują mnie również inne przykłady.

— Noam Zeilberger
źródło

Nigdy nieopublikowany dowód na to, że Agol używa zszywanych hierarchii, jest krótko podsumowany w niedawnej ankiecie Lackenby: people.maths.ox.ac.uk/lackenby/ekt11214.pdf

— Arnaud

R^{3}

$\mathbb{R}^3$

R^{3}

$\mathbb{R}^3$

S^{3}

$\mathbb{S}^3$

dziękuję za twoją precyzję: umieściłem ją w tekście.

— Noam Zeilberger

Być może tutaj jest gęsta, ale nie jest jasne, dlaczego wyniki są scharakteryzowane w odpowiedzi jako mówienie o wiązaniu / nieczułości „byciu NP-twardym”, a nie „byciu NP”, ponieważ o ile widzę w streszczeniu, twierdzą że problemy są w NP, ale nie że są również NP-Complete.

— Abel Molina,

nie, masz rację, byłem po prostu gęsty. Naprawiono teraz.

— Noam Zeilberger,