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.GGπ1(S3)GG