Existe-t-il des formulations théoriques de nœuds de problèmes complets de NP?

Existe-t-il des problèmes NP complets (ou même NP-durs, ou NP) qui ont de bonnes propriétés topologiques à étudier? Les problèmes NP ont-ils des formulations théoriques de nœuds? Nous connaissons les résultats # du polynôme de Jones. Les problèmes de graphes (plongements?), En particulier les colorations des graphiques, peuvent avoir de belles propriétés théoriques de nœuds. Il s'agit d'une question ouverte, et toute référence à ce sujet est appréciée.$P$

Vous pouvez jeter un œil à:

Peter Golbus, Robert W. McGrail, Tomasz Przytycki, Mary Sharac et Aleksandar Chakarov. 2009. Les nœuds toriques tricolores sont complets NP . Dans les actes de la 47e Conférence régionale annuelle du Sud-Est (ACM-SE 47). ACM, New York, NY, USA,, article 42, 6 pages.

Résumé: Ce travail présente une méthode pour associer une classe de problèmes de satisfaction de contraintes à un nœud tridimensionnel. Étant donné un noeud, on peut construire un noeud quandle, qui est généralement une algèbre libre infinie. La collection de problèmes souhaitée est dérivée de l'ensemble des relations invariantes sur le nœud quandle, en appliquant la théorie qui relie les algèbres finies aux problèmes de satisfaction des contraintes. Cela nous permet de développer des notions de quandles et de nœuds traitables et NP-complets. En particulier, nous montrons que tous les nœuds de tore tricolores et tous, mais au plus 2 nœuds non triviaux avec 10 croisements ou moins, sont NP-complets.

et également à son rapport fondateur:

P. Golbus, RW McGrail, M. Merling, K. Ober, M. Sharac et J. Wood. La classe des problèmes de satisfaction des contraintes sur un nœud . Numéro de rapport technique BARD-CMSC-2008-01, Bard College, 2008.

Il y a quelques références dans le premier paragraphe de

• Marc Lackenby. Une limite supérieure polynomiale sur Reidemeister se déplace. arXiv: 1302.0180

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

• Joel Hass, Jeffrey C. Lagarias, Nicholas Pippenger. La complexité informatique des problèmes de nœuds et de liens. J. ACM 46 (1999) 185-211. arXiv: math / 9807016

• Greg Kuperberg. La nouure est en NP, modulo GRH. Décembre 2011, révisé en janvier 2014. arXiv: 1112.0845

$g$

• Ian Agol, Joel Hass, William Thurston. Le GENRE A 3 COLLECTEURS est complet NP. STOC 2002. Lien ACM

Je suis également intéressé par d'autres exemples.