Русская Википедия:Задача развязывания

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

Файл:Unknots.svg
Две простые диаграммы тривиального узла
Файл:Thistlethwaite unknot.svg
Запутанная диаграмма тривиального узла (узел Морвена Сислвайта)
Файл:Ochiai unknot.svg
Тривиальный узел Отиаи

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

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

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

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

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

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

Некоторые алгоритмы решения задачи развязывания основываются на теории Хакена Шаблон:Не переведено 5:

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

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

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

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

См. также

Примечания

Шаблон:Примечания

Литература

Ссылки

Шаблон:Теория узлов

Шаблон:Rq

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

  1. ↑ Упомянуто как «частное сообщение» [15] в списке ссылок статьи Куперберга (Kuperberg, 2014).
Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Задача_развязывания&oldid=9894546