Złożoność właściwości topologicznych.

Jestem informatykiem biorącym udział w kursie na temat topologii (posypka topologii punktowej mocno przyprawionej teorią kontinuum). Zainteresowały mnie problemy decyzyjne testujące opis przestrzeni (uproszczeniem) dla właściwości topologicznych; zachowane do homeomorfizmu.

Wiadomo na przykład, że określenie rodzaju węzła znajduje się w PSPACE i jest NP-twarde. (Agol 2006; Hass, Lagarias, Pippenger 1999)

Inne wyniki mają więcej bardziej ogólne odczucie: AA Markov (syn z Markowa) wykazały, że w 1958 roku badania dwie przestrzenie dla homeomorfizmu w wymiarach lub nowszy, jest nierozstrzygalny (pokazując nierozstrzygalności dla 4-rozmaitości). Niestety ten ostatni przykład nie jest doskonałym przykładem mojego pytania, ponieważ dotyczy samego problemu homeomorfii, a nie właściwości zachowanych w homeomorfizmie.$5$

Wydaje się, że jest dużo pracy w „topologii niskiego wymiaru”: teorii węzłów i grafów. Zdecydowanie interesują mnie wyniki z topologii niskiego wymiaru, ale bardziej interesują mnie wyniki uogólnione (wydają się rzadkie).

Najbardziej interesują mnie problemy, które są średnio trudne, ale zachęcam do wypisania problemów, o których nie wiadomo.

Jakie wyniki są znane na temat złożoności obliczeniowej właściwości topologicznych?

Topologia obliczeniowa obejmuje ogromną liczbę badań. Pełne podsumowanie każdego wyniku złożoności byłoby niemożliwe. Ale aby dać ci mały gust, pozwól mi rozwinąć twój przykład.

W 1911 r. Max Dehn postawił problem słowny dla precyzyjnie przedstawionych grup : czy biorąc pod uwagę ciąg znaków nad alfabetem generatora, czy reprezentuje on element tożsamości? Rok później Dehn opisał algorytm problemu słownego w podstawowych grupach powierzchni orientowalnych; równoważnie Dehn opisał, jak zdecydować, czy dany cykl na danej orientowanej powierzchni jest kurczliwy. Prawidłowo zaimplementowany algorytm Dehna działa w czasie . W tym samym artykule z 1912 r. Dehn stwierdził, że „Rozwiązanie problemu słownego dla wszystkich grup może być tak samo niemożliwe, jak rozwiązanie wszystkich problemów matematycznych”.$O(n)$

W 1950 r. Turing udowodnił, że problem słowny w doskonale przedstawionych półgrupach jest nierozstrzygalny, dzięki zmniejszeniu problemu zatrzymania (zaskoczenie, zaskoczenie).

Opierając się na wynikach Turinga, Markov udowodnił w 1951 r., Że każda nietrywialna własność skończonych prezentacji półgrup jest nierozstrzygalna. Właściwość grup jest nietrywialna, jeśli jakaś grupa ma właściwość, a inna nie. Informatycy teoretyczni znają podobny wynik funkcji cząstkowych jak „Twierdzenie Rice'a”.

W 1952 r. Novikov udowodnił, że problem słowny w skończonych grupach jest nierozstrzygalny, co dowodzi, że intuicja Dehna była prawidłowa. Ten sam wynik został niezależnie udowodniony przez Boone'a w 1954 roku i Brittona w 1958 roku.

W 1955 r. Adyan udowodnił, że każda nietrywialna własność przedstawionych grup jest nierozstrzygalna. Ten sam wynik został niezależnie udowodniony przez Rabina w 1956 r. (Tak, ten Rabin.)

Wreszcie w 1958 r. Markov opisał algorytmy konstruowania dwuwymiarowych kompleksów komórkowych i czterowymiarowych rozmaitości z dowolną pożądaną grupą podstawową, biorąc pod uwagę prezentację grupy jako dane wejściowe. Ten wynik natychmiast sugerował, że ogromna liczba problemów topologicznych jest nierozstrzygalna, w tym następujące:

• Czy dany cykl w danym dwuwymiarowym kompleksie jest kurczliwy? (To jest słowo problem.)
• Czy dany kompleks 2 jest po prostu podłączony? („Czy ta grupa jest trywialna?”)
• Czy dany cykl w danym 4-rozmaitym kurczy się?
• Czy dany 4-kolektorowy jest kurczliwy?
• Czy dany 4-kolektorowy homeomorficzny do konkretnego 4-kolektorowego (skonstruowany przez Markowa)?
• Czy dany 5-kolektorowy homeomorficzny z 5-kulą (lub jakimkolwiek innym stałym 5-kolektorem, który wybierzesz)?
• Czy dany kompleks 6 jest różnorodny?

Moja ulubiona konsekwencja tych wyników jest nowsza i bardziej subtelna: nie można rozstrzygnąć, czy dana grupa przedstawiona w sposób ostateczny jest podstawową grupą 3-różnorodną. Niedawny dowód Perelmana na hipotezę geometryzacji Thurstona implikuje istnienie algorytmu określającego, czy dany 3-rozmaitość ma trywialną grupę podstawową. (Jak wskazuje @SamNead, wyniki Rubensteina i Cassona sugerują algorytm działający w czasie wykładniczym). Jeśli dana grupa nie jest grupą potrójną, wówczas nie może być trywialna, ponieważ jest trywialny. Tak więc, jeśli możesz zdecydować, czy jest 3-różnorodną grupą, możesz zdecydować, czy jest trywialne, co jest niemożliwe.$G$$G$$\pi_1(S^3)$$G$$G$

Ryan Budney rozpoczął podobne dyskusje w MathOverFlow:

/mathpro/35946/how-expensive-is-knowledge-knots-links-3-and-4-manifold-al algorytmy

/mathpro/144158/what-is-the-state-of-the-art-for-alametermic-knot-simplification/145927

i na Wikipedii:

http://en.wikipedia.org/wiki/Talk:Computational_topology