Czy problem rozpoznawania 3-sferycznego NP-jest kompletny?

Wiadomo, że określenie, czy dany triangulowany 3-kolektor jest 3-kulą, znajduje się w NP, dzięki pracy Saula Schleimera w 2004 r .: „Rozpoznanie sfery leży w NP” arXiv: math / 0407047v1 [mat.GT] . Zastanawiam się, czy ustalono, że jest to kompletne NP w ciągu ostatnich pięciu czy sześciu lat? Analogiczne problemy, takie jak problem z 3-rozmaitym rodzajem węzła, pokazano jako NP-zupełne.

Jeśli jest NP-kompletny, to czy nie udowodniłbyś, że żaden zestaw (jednorodnie) obliczalnych niezmienników w czasie wielomianowym 3-różnorodnych nie odróżnia 3-sfer od innych 3-różnorodnych. Byłbym bardzo zaskoczony, gdyby to wiadomo.

Żeby dodać odpowiedź Petera: Hass, Lagarias i Pippenger wykazali, że problem nierozłączania węzłów w trójkuli jest w NP. Ian Agol udowodnił, że nierozstrzygający problem tkwi w ko-NP (ale zobacz jego komentarze na temat MathOverflow). Wydaje mi się, przynajmniej dla mnie, że problem z rozpoznawaniem trzech sfer jest bardziej zbliżony do nierozłączania niż do rodzaju węzłów w ogóle trójdzielnych. (Ponieważ jest to potwierdzone przez obecność dodatniej powierzchni charakterystycznej dla Eulera).

Dlatego postawiłbym, że rozpoznawanie trzech sfer jest również w ko-NP. Krokiem w tym kierunku byłoby wykazanie, że rozpoznawanie nieredukowalnych, toroidalnych rozmaitości odbywa się w NP, bezpośrednio za Agol. Nieco silniejsze byłoby wykazanie, że rozpoznanie różnorodności Hakena leży w NP. Oddzielenie trzech sfer od nieredukowalnych, nie toroidalnych rozmaitości jest trudniejsze. Być może jednak trzeba tam zastosować Geometrizację - jeśli kolektor jest zamknięty, orientowalny, nieredukowalny i atoroidalny, wówczas ma jedną z ośmiu geometrii Thurstona. Być może łatwo jest potwierdzić wszystkie geometryczne, ale nie-hiperboliczne rozmaitości, powiedzmy przez prawie normalne podziały Heegaarda. (Chociaż granice złożoności Hassa, Lagariasa i Pippengera musiałyby zostać jakoś zastąpione).

Potwierdzenie, że trójdzielny ma strukturę hiperboliczną, brzmi trudniej. Sugerują się dwa pomysły:$M$

Idąc za pomysłami Gabai (i oczywiście Thurstona), można poszukać prawidłowej prostej krzywej zamkniętej, aby wywiercić , aby uzyskać kolektor z granicą torusa. Poświadczenie struktury hiperbolicznej jest znacznie łatwiejsze i można nawet zapisać wystarczającą ilość informacji, aby udowodnić, że wypełnienie celu odzyskania nie niszczy hiperboliczności.$M$$N$$N$$N$$M$

Znacznie mniej rozsądne podejście jest udowodnić wirtualny Haken przypuszczenie w taki sposób, że albo a) get wielomian wielkości granice dotyczące stopnia pokrywy lub B), dowiedzieć się czegoś o niezwykle przydatnych .$M$

Ten artykuł pokazuje (choć tego nie zweryfikowałem), że rozpoznawanie 3-sferyczne * jest w koNP przy założeniu GRH:

Raphael Zentner. Homologia całkowita 3-sfery dopuszczają nieredukowalne reprezentacje w . $SL(2,\mathbb{C})$arXiv: 1605.08530 [mat.GT], 2016

(Możliwe zainteresowanie: dokument uzupełniający arXiv: 1610.04092 [mat.GT] wykorzystuje to do opracowania algorytmu wykorzystującego zasady Grobnera.)

* Technicznie stwierdzono, że rozpoznawanie 3-sfery wśród liczb całkowitych homologii 3-sferowej jest w koNP przy założeniu GRH. Nie jestem ekspertem w tej dziedzinie, ale wydaje mi się jasne, że można obliczyć homologię liczb całkowitych, biorąc pod uwagę triangulację w czasie wieloczasowym, a jeśli homologia liczb całkowitych nie pasuje do 3-kuli, to zdecydowanie nie jest 3-kula.