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.
cc.complexity-theory
reference-request
open-problem
topology
Joseph O'Rourke
źródło
źródło
Odpowiedzi:
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.
źródło
Ż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
źródło
Ten artykuł pokazuje (choć tego nie zweryfikowałem), że rozpoznawanie 3-sferyczne * jest w koNP przy założeniu GRH:
(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.
źródło