Проблема с развязыванием узлов

Нерешенная задача по математике :

Можно ли распознать развязки за полиномиальное время?

(еще нерешенные задачи по математике)

Две простые схемы развязывания узла

Сложная диаграмма без узлов, автор Морвен Тистлтуэйт.

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

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

Первые шаги к определению сложности вычислений были предприняты для доказательства того, что проблемав более крупных классах сложности, которые содержат класс P. Используя нормальные поверхности для описания поверхностей Зейферта данного узла, Хасс, Лагариас и Пиппенгер (1999) показали, что проблема развязывания относится к классу сложности NP . Хара, Тани и Ямамото (2005) заявили о более слабом результате, что развязывание происходит в AM ∩ co-AM ; однако позже они отказались от этого утверждения. В 2011 году Грег Куперберг доказал, что (при условии обобщенной гипотезы Римана ) проблема развязывания находится в co-NP , а в 2016 году Марк Лакенби предоставил безоговорочное доказательство членства в со-НП.

В 2021 году Лакенби анонсировал алгоритм распознавания узлов, который, по его утверждению, работает за квазиполиномиальное время . По состоянию на май 2024 года результат не был опубликован в рецензируемой литературе.

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

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

Несколько алгоритмов, решающих проблему развязывания, основаны на Хакена теории нормальных поверхностей :

• Алгоритм Хакена использует теорию нормальных поверхностей для поиска диска, границей которого является узел. Первоначально Хакен использовал этот алгоритм, чтобы показать, что развязывание разрешимо, но не анализировал его сложность более подробно.
• Хасс, Лагариас и Пиппенджер показали, что множество всех нормальных поверхностей может быть представлено целыми точками многогранного конуса и что поверхность, свидетельствующая о незаузленности кривой (если она существует), всегда может быть найдена на одном из крайних лучей. этого конуса. Следовательно, методы перебора вершин можно использовать для перечисления всех крайних лучей и проверки, соответствует ли какой-либо из них ограничивающему диску узла. Хасс, Лагариас и Пиппенджер использовали этот метод, чтобы показать, что незавязанность находится в NP; более поздние исследователи, такие как Бертон (2011a), усовершенствовали свой анализ, показав, что этот алгоритм может быть полезен (хотя и не с полиномиальным временем), поскольку его сложность представляет собой одноэкспоненциальную функцию низкого порядка от количества пересечений.
• Алгоритм Бирмана и Хирша (1998) использует слоения кос , несколько иной тип структуры, чем нормальная поверхность. Однако для анализа его поведения они возвращаются к теории нормальной поверхности.

Другие подходы включают в себя:

• Число ходов Райдемейстера, необходимое для изменения диаграммы с узлами на стандартную диаграмму с узлами, не более чем полиномиально по числу пересечений. Следовательно, перебор всех последовательностей ходов Райдемейстера может обнаружить незавязку за экспоненциальное время.
• Аналогично, любые две триангуляции одного и того же узла могут быть соединены последовательностью движений Пахнера, длина которых не более чем двукратно экспоненциальна по числу пересечений. Следовательно, можно определить, является ли узел узлом, проверив все последовательности ходов Пахнера этой длины, начиная с дополнения к данному узлу, и определив, преобразует ли какой-либо из них дополнение в стандартную триангуляцию полнотора . . Время для этого метода будет тройным экспоненциальным; однако экспериментальные данные показывают, что эта оценка очень пессимистична и что требуется гораздо меньше ходов Пахнера.
• Любое дуговое представление узла можно монотонно упростить до минимального с помощью элементарных ходов. Таким образом, перебор методом перебора среди всех дуг-представлений не большей сложности дает одноэкспоненциальный алгоритм решения задачи развязывания.
• Остаточная конечность группы узлов (которая следует из геометризации многообразий Хакена ) дает алгоритм: проверить, имеет ли группа нециклический конечный групповой фактор. Эта идея используется в результате Куперберга о том, что проблема развязывания находится в co-NP.
• Узел Гомология узла Флоера определяет род узла, который равен 0 тогда и только тогда, когда узел является развязным узлом. Комбинаторная версия гомологии узла Флоера позволяет вычислить его ( Manolescu, Ozsváth & Sarkar 2009 ).
• Гомология Хованова обнаруживает узел в соответствии с результатом Кронхаймера и Мровки . Сложность гомологии Хованова по меньшей мере не уступает #P-трудной задаче вычисления полинома Джонса , но на практике ее можно вычислить с использованием алгоритма и программы Бар-Натана (2007) . Бар-Натан не проводит строгого анализа своего алгоритма, но эвристически оценивает его как экспоненциальную ширину пути диаграммы пересечений, которая, в свою очередь, не более чем пропорциональна квадратному корню из числа пересечений.

Понимание сложности этих алгоритмов является активной областью исследований.

См. также

• Алгоритмическая топология
• Число развязывания

Ссылки

• Бар-Натан, Дрор (2007), «Вычисления быстрых гомологий Хованова», Журнал теории узлов и ее разветвлений , 16 (3): 243–255, arXiv : math.GT/0606318 , doi : 10.1142/S0218216507005294 , MR   2320156 , S2CID   17036344 .
• Бирман, Джоан С .; Хирш, Майкл (1998), «Новый алгоритм распознавания узла», Geometry and Topology , 2 : 178–220, arXiv : math/9801126 , doi : 10.2140/gt.1998.2.175 , S2CID   17776505 .
• Бертон, Бенджамин А. (2011a), «Максимально допустимые грани и асимптотические границы для пространства решений нормальной поверхности» (PDF) , Журнал комбинаторной теории , серия A, 118 (4): 1410–1435, arXiv : 1004.2605 , doi : 10.1016/j.jcta.2010.12.011 , MR   2763065 , S2CID   11461722 .
• Бертон, Бенджамин (2011b), «Граф Пахнера и упрощение трехсферных триангуляций», Proc. 27-й симпозиум ACM по вычислительной геометрии , стр. 153–162, arXiv : 1011.4169 , doi : 10.1145/1998196.1998220 , S2CID   382685 .
• Дынников, Иван (2006), «Дужные представления связей: монотонное упрощение», Fundamenta Mathematicae , 190 : 29–76, arXiv : math/0208153 , doi : 10.4064/fm190-0-3 , S2CID   14137437 .
• Хакен, Вольфганг (1961), «Теория нормальных поверхностей», Acta Mathematica , 105 : 245–375, doi : 10.1007/BF02559591 .
• Хара, Масао; Тани, Сейичи; Ямамото, Макото (2005), «Развязка происходит в AM ∩ co-AM», Proc. 16-й симпозиум ACM-SIAM по дискретным алгоритмам (SODA '05) , стр. 359–364 .
• Хасс, Джоэл ; Лагариас, Джеффри С .; Пиппенгер, Николас (1999), «Вычислительная сложность задач узлов и связей», Journal of the ACM , 46 (2): 185–211, arXiv : math/9807016 , doi : 10.1145/301970.301971 , MR   1693203 , S2CID   125854 .
• Хасс, Джоэл ; Лагариас, Джеффри К. (2001), «Количество ходов Райдемейстера, необходимое для развязывания узлов», Журнал Американского математического общества , 14 (2): 399–428, arXiv : math/9807012 , doi : 10.1090/S0894-0347- 01-00358-7 , МР   1815217 , S2CID   15654705 .
• Каварабаяси, Кеничи ; Крейцер, Стефан; Мохар, Боян (2010), «Бесзвенные и плоские вложения в трехмерном пространстве и проблема узлов» (PDF) , Proc. Симпозиум ACM по вычислительной геометрии (SoCG '10) , стр. 97–106, doi : 10.1145/1810959.1810975 , S2CID   12290801 .
• Кронхаймер, Питер; Мровка, Томаш (2011), «Гомологии Хованова - детектор узла», Publications Mathématiques de l'IHÉS , 113 (1): 97–208, arXiv : 1005.4346 , doi : 10.1007/s10240-010-0030-y , S2CID   119586228
• Куперберг, Грег (2014), «Завязанность в NP, по модулю GRH», Успехи в математике , 256 : 493–506, arXiv : 1112.0845 , doi : 10.1016/j.aim.2014.01.007 , MR   3177300 , S2CID   126 34367 .
• Лакенби, Марк (2015), «Полиномиальная верхняя граница движений Райдемайстера», Annals of Mathematics , Second Series, 182 (2): 491–564, arXiv : 1302.0180 , doi : 10.4007/annals.2015.182.2.3 , MR   3418524 , S2CID   119662237 .
• Лакенби, Марк (2021), «Эффективная сертификация узловатости и нормы Терстона», Advances in Mathematics , 387 : 107796, arXiv : 1604.00290 , doi : 10.1016/j.aim.2021.107796 , S2CID   119307517 .
• Манолеску, Чиприан ; Озсват, Питер С .; Саркар, Сухарит (2009), «Комбинаторное описание гомологии узла Флоера», Annals of Mathematics , Second Series, 169 (2): 633–660, arXiv : math/0607691 , Bibcode : 2006math......7691M , doi : 10.4007/annals.2009.169.633 , MR   2480614 , S2CID   15427272 .
• Миятович, Александар (2005), «Простые структуры узловых дополнений», Mathematical Research Letters , 12 (6): 843–856, arXiv : math/0306117 , doi : 10.4310/mrl.2005.v12.n6.a6 , MR   2189244 , S2CID   7726354