Сложность топологических свойств.

Я ученый, изучающий топологию (разброс топологии точечных множеств, сильно приправленный теорией континуума). Я заинтересовался решением проблем, проверяя описание пространства (с помощью симплексов) для топологических свойств; сохранились до гомеоморфизма.

Например, известно, что определение рода узла находится в PSPACE и является NP-Hard. (Agol 2006; Hass, Lagarias, Pippenger 1999)

Другие результаты имеют еще более общего ощущение: А. А. Марков (сын в Марковой) показала в 1958 году , что тестирование двух пространств гомеоморфа в размерах или выше неразрешимое (показывая неразрешимость для 4-многообразий). К сожалению, этот последний пример не является идеальным примером моего вопроса, поскольку он касается самой проблемы гомеоморфности, а не свойств, сохраняющихся при гомеоморфизме.$5$

Похоже, что в «топологии низких измерений» много работы: теория узлов и графов. Я определенно интересуюсь результатами низкоразмерной топологии, но больше интересуюсь обобщенными результатами (они кажутся редкими).

Меня больше всего интересуют проблемы, которые в среднем относятся к NP-Hard, но я чувствую, что рекомендуется перечислить проблемы, о которых известно, что это не так.

Какие результаты известны о вычислительной сложности топологических свойств?

Вычислительная топология охватывает огромный объем исследований. Полное изложение результатов любой сложности было бы невозможно. Но чтобы дать вам небольшой вкус, позвольте мне расширить ваш пример.

$O(n)$

В 1950 году Тьюринг доказал, что проблема слов в конечно представленных полугруппах неразрешима путем сокращения из проблемы остановки (удивление, удивление).

Опираясь на результат Тьюринга, Марков доказал в 1951 г., что каждое нетривиальное свойство конечно-представленных полугрупп неразрешимо. Свойство групп нетривиально, если какая-то группа имеет свойство, а другая - нет. Теоретическим компьютерным ученым известен тот же результат о частичных функциях, что и «Теорема Райса».

В 1952 году Новиков доказал, что проблема слов в конечно представленных группах неразрешима, доказав тем самым, что интуиция Дена была правильной. Тот же результат был независимо доказан Бунем в 1954 году и Бриттоном в 1958 году.

В 1955 году Адьян доказал, что каждое нетривиальное свойство конечно-определенных групп неразрешимо. Тот же результат был доказан независимо Рабином в 1956 году. (Да, этот Рабин.)

Наконец, в 1958 году Марков описал алгоритмы для построения 2-мерных клеточных комплексов и 4-мерных многообразий с любой желаемой фундаментальной группой, учитывая представление группы в качестве входных данных. Этот результат сразу подразумевает, что огромное количество топологических проблем неразрешимо, включая следующие:

• Является ли данный цикл в данном 2-мерном комплексе стягиваемым? (Это проблема слова.)
• Является ли данный 2-комплекс просто связным? («Эта группа тривиальна?»)
• Является ли данный цикл в данном 4-многообразии стягиваемым?
• Является ли данный 4-многообразный стягиваемым?
• Является ли данное 4-многообразие гомеоморфным конкретному 4-многообразию (построенному Марковым)?
• Является ли данное 5-многообразие гомеоморфным 5-сфере (или любому другому фиксированному 5-многообразию, которое вы выберете)?
• Является ли данный 6-комплекс многообразием?

$G$$G$$\pi_1(S^3)$$G$$G$

Райан Будни начал подобные обсуждения в MathOverFlow:

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

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

и в Википедии:

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