Википедия

Задача развязывания

Задача развязывания — задача алгоритмического распознавания тривиального узла если задано некоторое представление узла, то есть диаграмма узла. Существует несколько видов алгоритмов развязывания. Основная нерешённая проблема — можно ли решить задачу за полиномиальное время, то есть, принадлежит ли задача классу сложности P.

Две простые диаграммы тривиального узла
Запутанная диаграмма тривиального узла (узел Морвена Сислвайта)
Тривиальный узел Отиаи

Вычислительная сложность править

Первые шаги в определении вычислительной сложности были предприняты в сторону доказательства, что задача принадлежит более сложным классам сложности, содержащим класс P. С использованием нормальных поверхностей[англ.] для описания поверхностей Зейферта заданного узла Хасс, Лагариас и Пиппенжер[1] показали, что задача развязывания принадлежит классу сложности NP. Хара, Тани и Ямамото[2] заявили, что развязывание принадлежит классу AM ∩ co-AM[англ.]. Позднее, однако, они отозвали своё заявление[3]. В 2011 Грег Куперберг[англ.] доказал, что (в предположении верности обобщённой гипотезы Римана) задача развязывания принадлежит классу co-NP[4].

Задача развязывания имеет ту же вычислительную сложность, что и проверка, является ли вложение неориентированного графа в евклидово пространство незацепленным[5].

Узел Отиаи, содержащий 139 вершин, например, был сперва развязан с помощью компьютера за 108 часов, но это время впоследствии сокращено до 10 минут[6]

Алгоритмы развязывания править

Некоторые алгоритмы решения задачи развязывания основываются на теории Хакена нормальных поверхностей[англ.]:

  • Алгоритм Хакена использует теорию нормальных поверхностей для поиска диска, граница которого заузлена. Хакен изначально использовал этот алгоритм, чтобы показать, что задача развязывания разрешима, но он не анализировал вычислительную сложность алгоритма детально.
  • Хасс, Лагариас и Пиппенджер показали, что множество всех нормальных поверхностей можно представить как целые точки в многогранном конусе и что поверхность, свидетельствующая о возможности развязывания кривой (если таковая существует), может быть всегда найдена на одном из крайних лучей этого конуса. Таким образом, методы перечисления вершин[англ.] могут быть использованы для перечисления всех крайних лучей и проверки, не являются ли они заузлёнными границами диска. Хасс, Лагариас и Пиппенджер использовали этот метод, чтобы показать, что нахождение развязывания принадлежит классу NP. Позднее исследователи, такие как Бартон[7] улучшили их анализ, показав, что этот алгоритм может быть полезен, имея невысокого порядка экспоненциальную сложность (как функцию от числа пересечений).
  • Алгоритм Бирмана и Хирша[8] использует расслоение кос[англ.], несколько другую структуру, отличную от нормальной поверхности. Однако для анализа их поведения они вернулись к теории нормальных поверхностей.

Другие подходы:

  • Число движений Рейдемейстера, необходимых для приведения диаграммы тривиального узла к стандартному виду не более чем полиномиально от числа пересечений[9]. Поэтому, полный поиск всех движений Рейдемейстера может обнаружить тривиальность узла за экспоненциальное время.
  • Похожим образом любые две триангуляризации одного и того же дополнения узла могут быть соединены последовательностью движений Пачнера длиной не больше двойного экспоненциала от числа пересечений[10]. Таким образом, можно определить, является ли узел тривиальным путём проверки последовательностей движений Пачнера этой длины, начиная с дополнения заданного узла, а затем проверки, нельзя ли какое-либо из этих движений преобразовать в стандартную триануляцию полного тора. Время этого метода должно бы быть трижды экспоненциальным, однако эксперименты показывают, что эти границы очень пессимистичны и нужно куда меньше движений Пачнера[11].
  • Остаточная конечность группы узла (которая следует из геометризации многообразий Хакена) даёт алгоритм — проверяем, не содержит ли группа нециклическую конечную факторгруппу. Эта идея используется в доказательстве Куперберга, что задача развязывания входит в класс co-NP.
  • Гомология Флоера[англ.] узла определяет род узла, который равен 0 тогда и только тогда, когда узел тривиален. Комбинаторная версия гомологии Флоера узла может быть вычислена[12].
  • Гомология Хованова[англ.] определяет тривиальность узла согласно результатам Кронхеймера[англ.] и Мровки[англ.][13]. Сложность гомологии Хованова по меньшей мере такая же как у #P-трудной задачи вычисления полинома Джонса, но он может быть вычислен с помощью алгоритма и программы Бар-Натана[14]. Бар-Натан не даёт строгого анализа своего алгоритма, но эвристически предполагает, что алгоритм экспоненциален от путевой ширины графа диаграммы пересечений, которая, в свою очередь, не больше квадратного корня от числа пересечений (с некоторым коэффициентом).

Изучение сложности этих алгоритмов активно продолжается.

См. также править

Примечания править

  1. ↑ Hass, Lagarias, Pippenger, 1999.
  2. ↑ Hara, Tani, Yamamoto, 2005.
  3. ↑ Упомянуто как «частное сообщение» [15] в списке ссылок статьи Куперберга (Kuperberg, 2014).
  4. ↑ Kuperberg, 2014.
  5. ↑ Kawarabayashi, Kreutzer, Mohar, 2010.
  6. ↑ Ladd, Kavraki, 2004.
  7. ↑ Burton, 2011a.
  8. ↑ Birman, Hirsch, 1998.
  9. ↑ Lackenby, 2015.
  10. ↑ Mijatović, 2005.
  11. ↑ Burton, 2011b.
  12. ↑ Manolescu, Ozsváth, Sarkar, 2009.
  13. ↑ Kronheimer, Mrowka, 2011.
  14. ↑ Bar-Natan, 2007.

Литература править

Ссылки править

Источник — https://ru.wikipedia.org/w/index.php?title=Задача_развязывания&oldid=128991845