Le problème de reconnaissance à 3 sphères est-il NP-complet?

On sait que déterminer si une variété triangulée donnée est ou non une sphère 3 est en NP, via les travaux de Saul Schleimer en 2004: "La reconnaissance de la sphère réside dans NP" arXiv: math / 0407047v1 [math.GT] . Je me demande si cela a été établi pour être NP-complet au cours des cinq ou six dernières années? Des problèmes analogues, tels que le problème du genre à 3 nœuds multiples, ont été montrés NP-complets.

S'il est NP-complet, alors n'auriez-vous pas prouvé qu'aucun ensemble d'invariants calculables en temps polynomial (uniformément) de 3 variétés ne distingue les 3 sphères des autres 3 variétés. Je serais très surpris si cela était connu.

Juste pour ajouter à la réponse de Peter: Hass, Lagarias et Pippenger ont montré que le problème de dénouement des nœuds dans les trois sphères était en NP. Ian Agol a prouvé que le problème de dénouement est en co-NP (mais voir ses commentaires sur MathOverflow). Il me semble, du moins pour moi, que le problème de la reconnaissance des trois sphères est beaucoup plus apparenté au dénouement qu'au nœud du genre en général à trois variétés. (Parce qu'il est certifié par la présence d'une surface caractéristique d'Euler positive.)

Je parierais donc que la reconnaissance à trois sphères est également en co-NP. Un pas dans cette direction serait de montrer que la reconnaissance des variétés toroïdales irréductibles est en NP, directement après Agol. Un peu plus fort serait de montrer que la reconnaissance multiple de Haken réside dans NP. Il est plus difficile de séparer les trois sphères des collecteurs non toroïdaux irréductibles. Mais peut-être que la chose à faire est d'utiliser la géométrie - si le collecteur est fermé, orientable, irréductible et atoroïdal, il possède l'une des huit géométries de Thurston. Il est peut-être facile de certifier toutes les variétés géométriques mais non hyperboliques, par exemple via des séparations Heegaard presque normales. (Bien que les limites de complexité de Hass, Lagarias et Pippenger devraient être remplacées, d'une manière ou d'une autre.)

$M$

$M$$N$$N$$N$$M$

$M$

Cet article montre (bien que je ne l'ai pas vérifié) que la reconnaissance à 3 sphères * est en coNP en supposant GRH:

$SL(2,\mathbb{C})$

(D'un intérêt possible: un article de suivi arXiv: 1610.04092 [math.GT] l' utilise pour développer un algorithme utilisant les bases de Grobner.)

* Techniquement, il est indiqué que la reconnaissance de la 3 sphère parmi les 3 sphères d'homologie entière est en coNP en supposant GRH. Je ne suis pas un expert dans ce domaine, mais il me semble clair que l'on peut calculer l'homologie entière étant donné une triangulation en poly-temps, et si l'homologie entière ne correspond pas à celle d'une sphère à 3 alors ce n'est certainement pas la 3-sphère.