Czy problem rozpoznawania 3-sferycznego NP-jest kompletny?

13

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.

Joseph O'Rourke
źródło
3
Obecnie wiadomo, że problemem jest także współ-NP, patrz zapowiedź J. Hassa, Nowe wyniki dotyczące złożoności rozpoznawania 3-sfery, Oberwolfach Rep. 9 (2012), no. 2, 1425 {1426.
Arnaud,
@Arnaud: Wszelkie aktualizacje na ten temat? Od tego czasu nie mogłem znaleźć od Hassa problemu. Najlepsze, co mogłem znaleźć, to wynik CoNP uwarunkowany GRH, który umieściłem w mojej nowej odpowiedzi, i wydaje się, że nie wspomina o Hassie :(.
Joshua Grochow
@JoshuaGrochow Przepraszam, mój komentarz był niedokładny, a twierdzenie Joela Hassa (zapomniałem też powiedzieć, że to było z G. Kuperbergiem) również zakładało, że GRH. O ile mi wiadomo, kompletny opis jeszcze się nie ukazał.
Arnaud,

Odpowiedzi:

15

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.

Peter Shor
źródło
3
W szczególności wynik twardości NP dowodziłby, że 3-sfera nie może być odróżniona od innych 3-sfer homologii w czasie wielomianowym.
Jeffε
7

Ż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.MNNNM

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

Sam Nead
źródło
3

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,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.

Joshua Grochow
źródło