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

27

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

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

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

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

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

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

Росс Снайдер
источник
1
Можете ли вы сформулировать конкретный вопрос?
Суреш Венкат
2
Прежде чем кто-либо выдвинет возражение, позвольте мне объяснить, почему я считаю, что этот вопрос является конкретным: я провел обычный поиск литературы и нашел относительно мало обращающихся к моему вопросу. Поэтому ответы на вопрос предполагают определенный уровень знаний. Кроме того, вычислительная топология неоспоримо по теме в этом ТКС SE.
Росс Снайдер
2
Поскольку результатом может быть список, это должен быть CW?
Суреш Венкат
5
Я думаю, что это отличный вопрос. Очень мало известно о вычислительной сложности проблем топологии, и я не верю, что она была собрана в одном месте (если это так, будет достаточно одного ответа, и вопрос не должен быть CW).
Питер Шор
3
Рассматривали ли вы «Алгоритмическую топологию и классификацию 3-многообразий» С.Матвеева? ( springer.com/matmatics/geometry/book/978-3-540-45898-2 Оглавление доступно для бесплатной загрузки)
Артем Пеленицын

Ответы:

27

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

O(n)

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

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

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

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

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

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

GGπ1(S3)GG

Jeffε
источник
Джефф. Спасибо. Это действительно хорошая вещь, и невероятно расширяет второй пример.
Росс Снайдер
Я добавил награду к вопросу не потому, что этот ответ не удивителен, а потому, что я стремлюсь поощрять больше ответов (особенно больше похоже на мой первый пример). Еще раз спасибо.
Росс Снайдер
Ваш аргумент в пользу неразрешимости быть 3-многообразной группой кажется мне немного шатким. Это не дает вам возможности построить 3-многообразие, для которого G является группой, но, может быть, есть какой-то способ ответить «да» или «нет», не создавая многообразие? Тогда Перельману больше не на что будет идти.
Дэвид Эппштейн
Вот более осторожное объяснение Генри Уилтона: ldtopology.wordpress.com/2010/01/26/…
Джеффс
1
@JeffE - Я не уверен, почему ты проигнорировал мой предыдущий комментарий. Там это алгоритм ехра время , чтобы решить , если фундаментальная группа (замкнутый связными) три-многообразий тривиально. Сказать «НЕТ границ известны сложности этого алгоритма» неправильно ... не так ли? Чего мне не хватает? Могу ли я попросить вас объяснить?
Сэм Нид