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$

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.

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.